#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int corrPos, corrState, l, r;
bool done[5005];
vector<int> switches;
void exploreCave(int N) {
for (int i=0; i < N; ++i) done[i] = false;
int S[N], D[N];
for (int i=0; i < N; ++i) {
switches.clear();
for (int j=0; j < N; ++j) if (!done[j]) switches.push_back(j);
for (int j=0; j < N-i; ++j) S[switches[j]] = 0;
corrState = (tryCombination(S) == i) ? 1 : 0;
for (int j=0; j < N-i; ++j) S[switches[j]] = corrState^1;
l = 0;
r = N-i-1;
corrPos = -1;
while (l <= r) {
int mid = (l+r)/2;
for (int j=l; j <= mid; ++j) S[switches[j]] = corrState;
int firstOpen = tryCombination(S);
for (int j=l; j <= mid; ++j) S[switches[j]] = corrState^1;
if (firstOpen == i) l = mid+1;
else {
corrPos = switches[mid];
r = mid-1;
}
}
done[corrPos] = true;
S[corrPos] = corrState;
D[corrPos] = i;
}
answer(S, D);
}
