做了1个小时,过样例
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, bool> exist;
unordered_map<int, bool> difference;
vector<vector<int>> input;
//玩家的下标是直接从1到n开始的
unordered_map<int, bool> out_game;
int main()
{
#ifndef ONLINE_JUDGE
FILE* s;
freopen_s(&s, "in.txt", "r", stdin);
#endif // !ONLINE_JUDGE
//我们现在首先需要把这个数据做一个拆分
//做差比较的过程需要加入,
//一个是做差的表,一个是已经加入数值的表
//一个数需要和这些表进行比较,必须要存在,如果不存在的话就直接判断错误
int n1, n2;
cin >> n1 >> n2;
//这两个数就要先做差然后加入做差的表
//做差的时候必须被减数较大,不能小于这些的数值,最后的结果不能是负的
//每轮的数据我们用嵌套的向量来保存用户的输入信息
exist[n1] = true;
exist[n2] = true;
if (n1 > n2) {
difference[n1 - n2] = true;
//exist[n1 - n2] = true;
}
else {
difference[n2 - n1] = true;
//exist[n2 - n1] = true;
}
//之后我们把整组的这个数据给加入的向量里面
int n, m;
cin >> n >> m;
//大小设置成n+1
input.resize(n + 1);
int t;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < m; j++) {
cin >> t;
input[i].push_back(t);
}
}
//在录入完用户数据以后需要按照一轮轮的进行处理,我们数据录入以后首先是要考虑会不会和已有的数据重复了
//在一轮轮的时候我们需要遍历每个玩家给出的数据,判断的标准就是
//轮次在遍历的时候是固定的,我们需要有一个数组来淘汰
//相关的内容,如果说玩家出局了,我们把向量清空来进行标记
//或者开一个out的数组,在查询之前首先进行检查
//一般来说不要把相关的原始数据清空,作为一个
//我们在读到这个相关的数据的时候,我们在做差完也需要把相关的数据加入存在数组
//存在数组里面有那么多的数据,
for (int i = 0; i < m; i++) {
vector<int> out;
//一轮里面可能需要淘汰多个的数据,在多轮结束以后,如果未被标记的话就认为是胜出的玩家
for (int j = 1; j <= n; j++) {//j代表的是玩家的下标
if (out_game[j] != true) {
if (exist[input[j][i]] != true) {
//如果元素已经存在的话,需要考虑其是否已经在系统之前探索的做差的范围里面
if (difference[input[j][i]] == true) {
//在做差的范围里面的话,需要把它已经存在,我们以后尽量用true来表示存在关系
//我们首先需要把这个元素和已经存在的那些元素进行做差,再把做差之后的结果加入
//到做差的集合里面,然后把这个元素标记到存在数组里面
for (auto it = exist.begin(); it != exist.end(); it++) {
if (it->first > input[j][i]) {
difference[it->first - input[j][i]] = true;
}
else {
difference[input[j][i] - it->first] = true;
}
}
exist[input[j][i]] = true;
}
else {
//如果不在做差的范围里面
out_game[j] = true;
out.push_back(j);
}
}
else {
//如果一个值已经存在,我们需要把这个用户标记为出局
out_game[j] = true;//j代表的是玩家的下标
out.push_back(j);
}
}
}
if (out.size() == 1) {
printf("Round #%d: %d is out.\n",i+1,out[0]);
}
else if (out.size() > 1) {
sort(out.begin(),out.end());
cout << out[0];
for (int i = 1; i < out.size(); i++) {
cout << " " << out[i];
}
cout << endl;
}
}
//在几轮做完以后,判断相关的数组
vector<int> winner;
for (int i = 1; i <= n; i++) {
if (out_game[i] != true) {
winner.push_back(i);
}
}
if(winner.size()!=0){
sort(winner.begin(), winner.end());
cout << "Winner(s):";
for (int i = 0; i < winner.size(); i++) {
cout << " " << winner[i];
}
cout << endl;
}
else {
cout << "No winner.";
}
return 0;
}