#include "cave.h"
#include <stdio.h>
void exploreCave(int N) {
int state[N];
int linked[N]; // switch i is linked to door #linked[i]
int def[N];
for(int i = 0; i < N; ++i) def[i] = 0, state[i] = linked[i] = -1;
for(int cur_door = 0; cur_door < N; ++cur_door){
int t = tryCombination(def)-1;
int s = (t >= cur_door || t == -2 ? 0 : 1);
int l = 0, r = N-1; // finding the first point where we set the state from start to that point and we can open the cur door
while(l < r){
int mid = (l+r)/2;
int trying[N];
for(int i = 0; i <= mid; ++i){
if(state[i] != -1) trying[i] = state[i];
else trying[i] = s;
}
for(int i = mid+1; i < N; ++i){
if(state[i] != -1) trying[i] = state[i];
else trying[i] = !s;
}
int t = tryCombination(trying)-1;
if(t >= cur_door || t == -2) r = mid;
else l = mid+1;
}
linked[l] = cur_door;
state[l] = def[l] = s;
}
answer(state, linked);
}
