#include "bits/stdc++.h"
#include "cave.h"
//#include "grader.c"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'
void exploreCave(int n) {
vi curr(n), initIdx(n), ansIdx(n, -1);
int qr[n] = {0};
int last = tryCombination(qr);
for_(i, 0, n) initIdx[i] = i;
for_(i, 0, n) {
int pt = 0;
if (last == -1 or last > i) {
for_(j, 0, curr.size()) curr[j] = 1-curr[j];
for_(j, 0, n) if (ansIdx[j] == -1) qr[j] = curr[pt++];
}
// cout << "starting " << i << " with assuming that it is closed when in query: ";
// for_(j, 0, n) cout << qr[j];
// cout << endl;
int l = 0, r = curr.size(), ans = -1;
while (l < r) {
int mid = (l+r)/2;
pt = 0;
for_(j, 0, n) if (ansIdx[j] == -1) {
if (pt <= mid) qr[j] = 1-curr[pt];
else qr[j] = curr[pt];
pt++;
}
if ((last = tryCombination(qr)) > i or last == -1) {
r = ans = mid;
} else l = mid+1;
// cout << "for mid " << mid << ": ";
// for_(j, 0, n) cout << qr[j];
// cout << " value: " << last << endl;
}
// cout << "got ans " << ans << " " << initIdx[ans] << endl;
qr[initIdx[ans]] = 1-curr[ans];
pt = 0;
for_(j, 0, n) if (ansIdx[j] == -1) {
curr[pt] = qr[j];
pt++;
}
last = tryCombination(qr);
// cout << "ending with qr: ";
// for_(j, 0, n) cout << qr[j];
// cout << " and value " << last << endl;
ansIdx[initIdx[ans]] = i;
curr.erase(curr.begin()+ans);
initIdx.erase(initIdx.begin()+ans);
}
// cout << "got final indices: " << endl;
// for (auto i: ansIdx) cout << i << " ";
// cout << endl;
int finIdx[n], finState[n];
for_(i, 0, n) {
finIdx[i] = ansIdx[i];
}
answer(qr, finIdx);
}
