#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int const MAXN = 5010;
void exploreCave(int N) {
bitset<MAXN> bio;
int S[N], D[N], Q[N];
memset(S, 0, sizeof S);
memset(D, 0, sizeof D);
memset(Q, 0, sizeof Q);
list<int> l;
for (int i = 0; i < N; ++i) {
l.push_back(i);
}
for (int i = 0; i < N; ++i) {
int a = tryCombination(S);
int state = 0;
if (a != -1 && a == i) {
state = 1;
}
int lo = 0, hi = N - i;
while (lo < hi - 1) {
int mid = (lo + hi) / 2;
int cnt = 0;
for (int j = 0; j < N; ++j) {
if (bio[j]) Q[j] = S[j];
}
for (auto j : l) {
if (cnt >= lo && cnt < mid) Q[j] = state;
else Q[j] = !state;
++cnt;
}
a = tryCombination(Q);
if (a != -1 && a == i) {
lo = mid;
} else {
hi = mid;
}
}
auto it = l.begin();
advance(it, lo);
S[*it] = state;
D[*it] = i;
bio[*it] = true;
l.erase(it);
}
answer(S, D);
}
