#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAXN = 5e3 + 10;
int ss[MAXN], perm[MAXN], comb[MAXN], ans[MAXN];
int test() {
int x = tryCombination(ss);
if (x != -1) return x;
return 1e9;
}
void exploreCave(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
ss[j] = 0;
for (int j = 0; j < i; ++j)
ss[perm[j]] = comb[perm[j]];
bool val;
if (test() > i) val = false;
else val = true;
//cerr << "DOOR " << i << " " << val << "\n";
int l = 0, r = n - 1;
while (l < r) {
int m = (l + r)/2;
for (int j = 0; j < n; ++j)
ss[j] = 0;
for (int j = l; j <= m; ++j)
ss[j] = 1;
for (int j = 0; j < i; ++j)
ss[perm[j]] = comb[perm[j]];
if (test() > i)
if (val) r = m;
else l = m + 1;
else if (val) l = m + 1;
else r = m;
}
//cerr << "POSITION " << l << "\n";
perm[i] = l;
comb[perm[i]] = val;
ans[l] = i;
}
answer(comb, ans);
}
