#include "cave.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define sc second
#define fr first
#define mk make_pair
#define pb push_back
using namespace std;
const int NN = (1e6 + 5);
const int inf = (1e9 + 7);
int n;
int ans[NN],s[NN],u[NN];
int rs[NN];
void exploreCave(int N) {
n = N;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) u[j] = 1;
for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];
int last = tryCombination(u);
int l = 0,r = n - 1,fl = 1;
while (r - l > 1) {
int m = (r + l) >> 1;
for (int j = m + 1; j <= r; j ++) u[j] = fl ^ 1;
for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];
int cur = tryCombination(u);
// for (int j = 0; j < n; j ++)
// cout << u[j] << " ";
// cout << endl;
// cout << l << " " << r << " " << cur << endl;
if ((cur != i && last != i) || (cur == i && last == i)) r = m;
else l = m + 1,fl ^= 1;
last = cur;
}
if (l == r) {
ans[i] = l;
s[l] = (last == i ? (fl ^ 1) : fl);
}
else {
u[r] = fl ^ 1;
for (int j = 0; j < i; j ++) u[ans[j]] = s[ans[j]];
int cur = tryCombination(u);
if ((cur == i && last == i) || (cur != i && last != i)) {
ans[i] = l;
s[l] = (cur == i ? (fl ^ 1) : (fl));
}
else {
ans[i] = r;
s[r] = (cur == i ? fl : (fl ^ 1));
}
}
}
for (int i = 0; i < n; i ++)
rs[ans[i]] = i;
answer(s,rs);
}
