#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void exploreCave(int N) {
int S[N], D[N];
bool vis[N + 1];
for(int i = 0; i < N; ++i) S[i] = 0, D[i] = i, vis[i] = 0;
auto ok = [&](int x, int r) -> bool {
int NS [N];
for(int i = 0; i < N; ++i) NS[i] = S[i];
for(int i = 0; i <= r; ++i){
if(!vis[i]) NS[i] ^= 1;
}
return tryCombination(NS) ^ x;
};
for(int i = 0; i < N; ++i){
int pos = tryCombination(S);
bool locked = 0;
if(pos == i) locked = 1;
int st = 0, en = N - 1, org = 0;
while(st <= en){
int mid = st + (en - st) / 2;
if(ok(i, mid)) org = mid, en = mid - 1;
else st = mid + 1;
}
S[org] ^= locked, vis[org] = 1, D[org] = i;
}
answer(S, D);
}
