#include "cave.h"
#include <vector>
using namespace std;
vector<int> L;
int S[5001], D[5001];
bool DONE[5001];
int binary(int s, int e, int i, int prev){
if (s == e) return s;
int mid = (s+e) >> 1;
for (int j=s; j<=mid; j++) S[L[j]] ^= 1;
int res = tryCombination(S);
if ((res == i) == (prev == i)) return binary(mid+1, e, i, res);
return binary(s, mid, i, res);
}
void exploreCave(int N) {
for (int i=0; i<N; i++){
L.clear();
for (int j=0; j<N; j++) if (!DONE[j]) L.push_back(j);
int m = L.size();
for (int j=0; j<m; j++) S[L[j]] = 0;
int prev = tryCombination(S);
int res = L[binary(0, m-1, i, prev)];
D[res] = i;
if (tryCombination(S) == i) S[res] ^= 1;
DONE[res] = 1;
}
answer(S, D);
}
