#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
const int N = 5024;
int n;
int s[N];
int d[N];
mt19937 rnd;
bitset<N> can, an;
int query() {
int t = tryCombination(s);
return t == -1 ? n : t;
}
const int K = 30;
int save[K];
int num = 0;
int bit() {
num %= K;
if (!num) {
int msk = (int)rnd();
for (int i = 0; i < K; ++i) {
save[i] = (msk >> i) & 1;
}
}
return save[num++];
}
void exploreCave(int nn) {
n = nn;
fill_n(d, N, -1);
for (int i = 0; i < n; ++i) {
vector<int> f;
can.reset();
for (int j = 0; j < n; ++j) {
if (d[j] == -1) {
f.push_back(j);
can.set(j);
}
}
int q = query();
while (can.count() > 8) {
// cout << can.size() << endl;
vector<int> vec;
an.reset();
for (int e : f) {
if (bit()) {
vec.push_back(e);
an.set(e);
s[e] ^= 1;
}
}
int t = query();
for (int e : vec) {
s[e] ^= 1;
}
assert(q >= i && t >= i);
if ((q == i) == (t == i)) {
can &= ~an;
} else {
can &= an;
}
}
for (int j = 0; j < n; ++j) {
if (!can.test(j)) {
continue;
}
s[j] ^= 1;
int t = query();
if ((q == i) == (t == i)) {
continue;
}
d[j] = i;
if (t == i) {
s[j] ^= 1;
}
break;
}
assert(query() > i);
}
answer(s, d);
}
#ifdef LC
#include "graderlib.c"
int main() {
N = init();
exploreCave(N);
printf("INCORRECT\nYour solution did not call answer().\n");
return 0;
}
#endif
