#include "cave.h"
void exploreCave(int N) {
int D[N], T[N], S[N];
bool type = 0;
for(int i = 0; i < N; i++){
D[i] = -1;
S[i] = 0;
T[i] = 0;
}
for(int cur = 0; cur < N; cur++){
int ini = 0, fim = N;
for(int i = 0; i < N; i++){
if(D[i] != -1) T[i] = S[i];
else T[i] = 1;
}
if(tryCombination(T) != cur) type = 1;
while(ini < fim - 1){
int mid = (ini + fim) >> 1;
for(int i = ini; i < mid; i++){
if(D[i] != -1) T[i] = S[i];
else T[i] = type;
}
for(int i = mid; i < fim; i++){
if(D[i] != -1) T[i] = S[i];
else T[i] = !type;
}
int last = tryCombination(T);
if(last == cur){
for(int i = ini; i < mid; i++){
if(D[i] != -1) T[i] = S[i];
else T[i] = !type;
}
for(int i = mid; i < fim; i++){
if(D[i] != -1) T[i] = S[i];
else T[i] = type;
}
ini = mid;
}
else fim = mid;
}
D[ini] = cur;
S[ini] = type;
}
answer(S, D);
}
