#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pr pair<int, int>
#define tri array<int, 3>
const int INF = 1e9 + 7;
int n;
void exploreCave(int N) {
n = N;
int pos[n], color[n], cur[n];
for (int i = 0; i < n; i++) {
pos[i] = 0; color[i] = 0; cur[i] = 0;
}
vector<bool> found(n, 0);
for (int i = 0; i < n; i++) {
int c;
int ttt = tryCombination(cur);
if (ttt > i || ttt == -1) c = 0;
else c = 1;
color[i] = c;
vector<int> idk;
for (int j = 0; j < n; j++) {
if (!found[j]) idk.pb(j);
}
int l = 0, r = idk.size(), m;
while (l < r) {
m = (l + r) / 2;
int temp[n];
for (int j = 0; j < n; j++) {
temp[j] = cur[j];
}
for (int j = 0; j < l; j++) {
temp[idk[j]] = (c ^ 1);
}
for (int j = l; j <= m; j++) {
temp[idk[j]] = c;
}
for (int j = m+1; j < idk.size(); j++) {
temp[idk[j]] = (c ^ 1);
}
int t = tryCombination(temp);
if (t > i || t == -1) r = m;
else l = m + 1;
}
int p = idk[l];
found[p] = 1;
pos[p] = i;
cur[p] = c;
}
answer(color, pos);
}
