#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 10;
int door[MAXN], position[MAXN], marc[MAXN];
bool p(int i, int j, int cur_door){
for(int k=i; k<=j; k++){
if(!marc[k]){
position[k] = 1 - position[k];
}
}
int ans = tryCombination(position);
for(int k=i; k<=j; k++){
if(!marc[k]){
position[k] = 1 - position[k];
}
}
return (ans == cur_door);
}
int bs(int n, int cur_door){
int l = 0, r = n - 1;
while(l < r){
int m = l + (r - l) / 2;
if(p(l, m, cur_door)) r = m;
else l = m + 1;
}
return r;
}
void exploreCave(int n){
for(int i=0; i<n; i++){
if(tryCombination(position) == i){
for(int j=0; j<n; j++){
if(!marc[j]){
position[j] = 1 - position[j];
}
}
}
int x = bs(n, i);
door[x] = i;
marc[x] = 1;
}
answer(position, door);
}
