#include<algorithm>
#include<vector>
#include "cave.h"
using namespace std;
const int MAXN = 5000 + 3;
int Switch[MAXN];
bool state[MAXN];
int n, tmp[MAXN];
int get(int num, int lim, int x) {
fill(tmp, tmp + lim + 1, x);
fill(tmp + lim + 1, tmp + n, x ^ 1);
for (int i = 0; i < num; ++i) tmp[Switch[i]] = state[i];
x = tryCombination(tmp);
return ~x ? x : n + 1;
}
int a[MAXN], b[MAXN]; // switch i match with door b[i]
void print_answer() {
for (int i = 0; i < n; ++i) {
b[Switch[i]] = i;
a[Switch[i]] = state[i];
}
answer(a, b);
}
void exploreCave(int MAXN) {
n = MAXN;
for (int i = 0; i < n; ++i) {
state[i] = get(i, n - 1, 1) > i ? 1 : 0;
int lo(0), hi(n - 2), m;
while (lo <= hi) {
m = (lo + hi) >> 1;
if (get(i, m, state[i]) > i)
hi = m - 1;
else lo = m + 1;
}
Switch[i] = hi + 1; // door i match with switch hi+1
}
print_answer();
}
