#include "interactive.h"
#include<set>
#include<map>
#include<cassert>
using namespace std;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
typedef long long ll;
vector<int> get_xor(vector<int> a) {
vector<int> b;
for (auto x : a) b.pb(x + 1);
auto q = get_pairwise_xor(b);
map<int, int> ma;
for (auto x : q) {
if (x != 0) ma[x]++;
}
vector<int> w;
for (auto x : ma) {
assert(x.y % 2 == 0);
while (x.y > 0) {
w.pb(x.x);
x.y -= 2;
}
}
return w;
}
vector<int> get_se(int a0, vector<int> b) {
auto c = b;
c.pb(0);
auto vb = get_xor(b), vc = get_xor(c);
map<int, int> ma;
for (auto x : vc) ma[x]++;
for (auto x : vb) ma[x]--;
vector<int> d;
for (auto x : ma) {
while (x.y--) d.pb(x.x ^ a0);
}
return d;
}
vector<int> guess(int n) {
vector<int> a(n);
a[0] = ask(1);
vector<int> b;
for (int i = 1; i < n; i++) b.pb(i);
vector<pair<pair<int, int>, vector<int>>> now{{{1, n - 1}, get_se(a[0], b)}};
while (!now.empty()) {
vector<int> gg;
for (auto x : now) {
if (x.x.x == x.x.y) a[x.x.x] = x.y[0]; else {
int mi = (x.x.x + x.x.y) / 2;
for (int i = mi + 1; i <= x.x.y; i++) gg.pb(i);
}
}
auto v = get_se(a[0], gg);
set<int> se;
for (auto x : v) se.insert(x);
vector<pair<pair<int, int>, vector<int>>> go;
for (auto x : now) {
if (x.x.x < x.x.y) {
int mi = (x.x.x + x.x.y) / 2;
vector<int> le, ri;
for (auto y : x.y) {
if (se.count(y)) ri.pb(y); else le.pb(y);
}
go.pb(mp(mp(x.x.x, mi), le));
go.pb(mp(mp(mi + 1, x.x.y), ri));
}
}
now = go;
}
return a;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Not correct size |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
640 KB |
Not correct size |
| 2 |
Halted |
0 ms |
0 KB |
- |
