#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
set<int> use;
int n;
pair<int, int> bsearch(int i, int s[]) {
vector<int> t;
for (auto u: use) t.push_back(u);
int cntrl = tryCombination(s);
if (cntrl == -1) cntrl = n+2;
int l = 0, r = t.size()-1;
while(l < r) {
int m = (l + r) / 2;
int ts[n];
for (int i = 0; i < n; i++) ts[i] = s[i];
for (int i = l; i <= m; i++) {
ts[t[i]] = 1-ts[t[i]];
}
int ans = tryCombination(ts);
if (ans == -1) ans = n + 2;
if (cntrl == i && ans > i) r = m;
else if (cntrl > i && ans == i) r = m;
else l = m + 1;
}
int corpos;
if (cntrl > i) corpos = s[t[l]];
else corpos = 1 - s[t[l]];
return {t[l], corpos};
}
void exploreCave(int x) {
n = x;
int s[n], d[n];
for (int i = 0; i < n; i++) s[i] = 0;
for (int i = 0; i < n; i++) use.insert(i);
for (int i = 0; i < n; i++) {
pair<int, int> ans = bsearch(i, s);
use.erase(ans.first);
s[ans.first] = ans.second;
d[ans.first] = i;
}
answer(s, d);
}
