this part of code get accepted in PAT, but 6/11 on Acwing due to TLE.
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int can_use[N * 2];
int guess_num[12][1010], person[12];
unordered_set<int> nouse_num;
int n, m;
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int x1, x2; cin >> x1 >> x2;
can_use[abs(x1 - x2)] = 1; //can_use[i] = 1 means this number is valid;
nouse_num.emplace(x1), nouse_num.emplace(x2); //record the existed nums
cin >> n >> m;
for (int i = 1; i <= n; i++ ) {
for (int j = 1; j <= m; j++ ) cin >> guess_num[i][j];
}
int cnt = 0; //num of person who is kicked out
for (int r = 1; r <= m; r++ ) {
for (int i = 1; i <= n; i++ ) { //search from top to bottom to ensure order
if (person[i]) continue; //ignore the person who has been kicked out before
int val = guess_num[i][r];
if (can_use[val] and !nouse_num.count(val)) { //get right answer and not existed before
for (int num: nouse_num) {
int new_num = abs(num - val);
can_use[new_num] = 1;
}
nouse_num.emplace(val); //current val can't be used again
}
else {
person[i] = 1; //kick out this person
if (cnt) cout << endl;
cout << "Round #" << r << ": " << i << " is out.";
cnt++ ;
}
}
}
if (cnt) cout << endl;
if (cnt == n) {
cout << "No winner.";
}
else {
cout << "Winner(s):";
for (int i = 1; i <= n; i++ ) {
if (!person[i]) {
cout << " " << i;
}
}
}
return 0;
}
delete can_use array, when checking value x, traversal nouse_num, suppose current value is t, then if (x + t) is in nouse_num, then we can make sure that x is correct because x + t - t = x
C++ (AC on ACWing)
#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int guess_num[12][1010], person[12];
set<int> nouse_num;
int n, m;
int main()
{
int x1, x2; scanf("%d%d", &x1, &x2);
nouse_num.emplace(x1), nouse_num.emplace(x2); //record the existed nums
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++ ) {
for (int j = 1; j <= m; j++ ) scanf("%d", &guess_num[i][j]);
}
int cnt = 0; //num of person who is kicked out
for (int r = 1; r <= m; r++ ) {
for (int i = 1; i <= n; i++ ) { //search from top to bottom to ensure order
if (!person[i]) { //ignore the person who has been kicked out before
int val = guess_num[i][r];
bool valid =false;
if (!nouse_num.count(val)){ //get right answer and not existed before
for (int num: nouse_num) {
int new_num = num + val;
if (nouse_num.count(new_num)) {
nouse_num.emplace(val);
valid = true;
break;
}
else {
valid = false;
}
}
}
if (!valid) {
person[i] = 1;
if (cnt) cout << endl;
cout << "Round #" << r << ": " << i << " is out.";
cnt++;
}//current val can't be used again
}
}
}
if (cnt) puts("");
if (cnt == n) {
printf("No winner.");
}
else {
printf("Winner(s):");
for (int i = 1; i <= n; i++ ) {
if (!person[i]) {
printf(" %d", i);
//cout << " " << i;
}
}
}
return 0;
}
```