#include "interactive.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define f first
#define s second
#define pb push_back
#define ins insert
#define trav(a,x) for (auto a:x)
#define F0R(i,a,b) for (int i = (a); i < (b); i++)
#define FOR(i,n) for (int i = 0; i < (n); i++)
#define rsz resize
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<pi,vi> T;
/*
vi hid;
int ask(int i) {
return hid[i - 1];
}
vi getPairwiseXor(vi pos) {
vi res;
trav(i,pos) trav(j,pos) res.pb(hid[i-1]^hid[j-1]);
return res;
}
*/
vi getXor(vi pos) {
/*cout << "pos: ";
for (auto it = pos.begin(); it != pos.end(); it++) {
if (it != pos.begin()) cout << ", ";
cout << *it;
}
cout << '\n';*/
vi POS;
trav(x,pos) POS.pb(x+1);
sort(all(POS));
vi ans = get_pairwise_xor(POS);
assert(sz(ans) == sz(pos)*sz(pos));
map<int,int> mp;
trav(x,ans) if (x != 0) mp[x]++;
vi res;
trav(x,mp) FOR(_,x.s/2) res.pb(x.f);
return res;
}
vi getSet(int a0, vi pos) {
vi POS = pos;
POS.pb(0);
vi ans = getXor(pos), ANS = getXor(POS);
map<int,int> mp;
trav(x,ans) mp[x]--; trav(x,ANS) mp[x]++;
vi res;
trav(x,mp) FOR(i,x.s) res.pb(x.f^a0);
return res;
}
vi guess(int n) {
vi a(n);
a[0] = ask(1);
vi pos;
F0R(i,1,n) pos.pb(i);
vector<T> layer={{{1,n-1},getSet(a[0],pos)}};
while (sz(layer)) {
/*cout << "layer: ";
for (auto it = layer.begin(); it != layer.end(); it++) {
if (it != layer.begin()) cout << ", ";
cout << "[" << it->f.f << ", " << it->f.s << "]";
}
cout << '\n';*/
vi POS;
trav(x,layer) {
if (x.f.f == x.f.s) a[x.f.f] = x.s[0]; else {
int mi = (x.f.f+x.f.s)/2;
F0R(i,x.f.f,mi+1) POS.pb(i);
}
}
/*cout << "POS: ";
for (auto it = POS.begin(); it != POS.end(); it++) {if (it != POS.begin()) cout << ", "; cout << *it;}
cout << '\n';*/
vi ANS = getSet(a[0],POS);
/*cout << "ANS: ";
for (auto it = ANS.begin(); it != ANS.end(); it++) {if (it != ANS.begin()) cout << ", "; cout << *it;}
cout << '\n';*/
set<int> ans;
trav(x,ANS) ans.ins(x);
vector<T> LAYER;
trav(x,layer) {
if (x.f.f != x.f.s) {
int mi = (x.f.f+x.f.s)/2;
vi lef,rig;
trav(y,x.s) if (ans.count(y)) lef.pb(y); else rig.pb(y);
LAYER.pb({{x.f.f, mi}, lef});
LAYER.pb({{mi+1, x.f.s}, rig});
}
}
layer = LAYER;
}
return a;
}
/*
int main() {
int t;
cin >> t;
while (t--) {
int n = rng()%9+2;
hid.rsz(0);
set<int> S;
FOR(i,n) {
int x = rng()%32;
while (S.count(x)) x = rng()%32;
S.ins(x);
hid.pb(x);
}
vi ans = guess(n);
if (ans != hid) {
cout << "hid: ";
for (auto it = hid.begin(); it != hid.end(); it++) {if (it != hid.begin()) cout << ", "; cout << *it;}
cout << "\nans: ";
for (auto it = ans.begin(); it != ans.end(); it++) {if (it != ans.begin()) cout << ", "; cout << *it;}
}
}
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Not correct size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
768 KB |
Not correct size |
| 2 |
Halted |
0 ms |
0 KB |
- |
