#include<iostream>
#include "cave.h"
using namespace std;
bool fijo[70005];
int arre[70005];
int ans[70005];
int posiciones[70005];
bool uno(int pos,int N){
for(int i=0;i<N;i++){
if(!fijo[i]){
arre[i]=1;
}else{
arre[i]=ans[i];
}
}
return(tryCombination(arre)==pos);
}
bool cerrada(int medio, int pos,bool valor,int N){
for(int i=0;i<=medio;i++){
if(!fijo[i]){
arre[i]=valor;
}else{
arre[i]=ans[i];
}
}
for(int i=medio+1;i<N;i++){
if(!fijo[i]){
arre[i]=!valor;
}else{
arre[i]=ans[i];
}
}
return(tryCombination(arre)==pos);
}
void bs(int indice,bool valor,int N){
int ini=0,res=0,fin=N-1,medio;
while(ini<=fin){
medio=(ini+fin)/2;
if(cerrada(medio,indice,valor,N)){
res=medio;
fin=medio-1;
}else{
ini=medio+1;
}
}
fijo[res]=true;
ans[res]=!valor;
posiciones[res]=indice;
}
void exploreCave(int N) {
for(int i=0;i<N;i++){
bs(i,uno(i,N),N);
}
answer(ans,posiciones);
}
