#include "interactive.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int MAXN = 100;
vector<int> guess(int n) {
vector <int> G;
vector <int> ans(n);
if (n <= 50) {
for (int i = 1; i <= n; i++)
ans[i-1] = ask(i);
return ans;
}
for (int i = 2; i <= n; i++)
G.pb(i);
vector <int> exp = get_pairwise_xor(G);
G.pb(1);
vector <int> all = get_pairwise_xor(G);
set <int> nums;
vector <int> arr, pos(n);
ans[0] = ask(1);
int j = 0;
for (int i = 0; i < exp.size(); i++, j++)
while (all[j] != exp[i])
nums.insert(all[j++] ^ ans[0]);
while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
for (int i : nums) arr.pb(i);
srand(time(NULL));
random_shuffle(arr.begin(), arr.end());
for (int i = 0; (1<<i) < n; i++) {
G.clear();
for (int j = 0; j < n; j++)
if (!(j&(1<<i))) G.pb(j+1);
vector <int> res = get_pairwise_xor(G);
vector <int> tmp, nxt;
for (int j = 0; j < n; j++) tmp.pb(j);
while (tmp.size() > G.size()) {
for (int j : tmp) {
int cnt = 0;
for (int k : tmp) {
int val = arr[j] ^ arr[k];
if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
cnt++;
}
if (cnt >= G.size()) nxt.pb(j);
}
if (tmp.size() == nxt.size()) break;
tmp = nxt;
nxt.clear();
}
vector <int> path[MAXN];
for (int j = 0; j < n; j++) path[j].clear();
for (int j : tmp) {
int cnt = 0;
for (int k : tmp) {
int val = arr[j] ^ arr[k];
if (res[res.size()-1] >= val && *lower_bound(res.begin(), res.end(), val) == val)
if (j != k) path[j].pb(k);
}
}
for (int j : tmp) {
if (path[j].size() == G.size()-1) {
bool flag = true;
set <int> appr;
for (int k : path[j]) appr.insert(k);
appr.insert(j);
for (int k : path[j]) {
int c = 0;
for (int p : path[k]) {
if (appr.count(p)) c++;
}
if (c != G.size()-1) flag = false;
}
if (flag) {
tmp = path[j];
tmp.pb(j);
}
}
}
for (int j = 0; j < n; j++) pos[j] += (1<<i);
for (int j : tmp) pos[j] -= (1<<i);
}
for (int i = 0; i < n; i++)
ans[pos[i]] = arr[i];
return ans;
}
Compilation message
Xoractive.cpp: In function 'std::vector<int> guess(int)':
Xoractive.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < exp.size(); i++, j++)
| ~~^~~~~~~~~~~~
Xoractive.cpp:34:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (j < all.size()) nums.insert(all[j++] ^ ans[0]);
| ~~^~~~~~~~~~~~
Xoractive.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | if (cnt >= G.size()) nxt.pb(j);
| ~~~~^~~~~~~~~~~
Xoractive.cpp:63:11: warning: unused variable 'cnt' [-Wunused-variable]
63 | int cnt = 0;
| ^~~
Xoractive.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if (c != G.size()-1) flag = false;
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
492 KB |
Output is correct |
| 2 |
Correct |
21 ms |
492 KB |
Output is correct |
| 3 |
Incorrect |
13 ms |
492 KB |
Output is not correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
