#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
void exploreCave(int N) {
int pos[N];
int doorindex[N];
bool ignore[N];
memset(ignore,0,sizeof(ignore));
int switches[N];
memset(switches,0,sizeof(switches));
for(ll cur = 0;cur < N;cur++){
for(ll i = 0;i < N;i++){
if(!ignore[i]){
switches[i] = 0;
}
}
ll front = tryCombination(switches);
ll correctpos;
if(front == cur){ //correctpos is 1
correctpos = 1;
ll high = N;
ll low = 0;
while(high - low > 1){
ll mid = (high + low) / 2;
for(ll i = 0;i < N;i++){
if(!ignore[i]){
if(i >= mid){
switches[i] = 1;
}else{
switches[i] = 0;
}
}
}
ll res = tryCombination(switches);
if(res == -1 || res > cur){
low = mid;
}else{
high = mid;
}
}
pos[low] = correctpos;
doorindex[low] = cur;
switches[low] = correctpos;
ignore[low] = 1;
}else{ //correctpos is 0
correctpos = 0;
ll high = N;
ll low = 0;
while(high - low > 1){
ll mid = (high + low) / 2;
for(ll i = 0;i < N;i++){
if(!ignore[i]){
if(i >= mid){
switches[i] = 1;
}else{
switches[i] = 0;
}
}
}
ll res = tryCombination(switches);
if(res != -1 && res == cur){
low = mid;
}else{
high = mid;
}
}
pos[low] = correctpos;
doorindex[low] = cur;
switches[low] = correctpos;
ignore[low] = 1;
}
}
answer(pos,doorindex);
}
