#include "cave.h"
///Binary Search
///Determine the position of switch-door
int temp[5005];
int s[5005];
int d[5005];
void turn_on_off(int N,int L,int R,int op) ///Turns on/off the switches in a range
{
for(int i=L;i<=R;i++){
if(s[i]==-1)
temp[i]=op;
else
temp[i]=s[i]; //If the door is already open, we
}
}
bool door_changed(int i,int inicial,int actual) ///Determines if door i changed
{
if(inicial==i){ //Initially closed
if(actual!=i) //Door opened
return true;
else
return false;
}
else{ //Initially open
if(actual==i) //Door closed
return true;
else
return false;
}
}
void openDoor(int N,int i) ///Search for the switch that opens door i
{
int L=0,R=N-1,mid;
int inicial=tryCombination(temp);
while(L<=R){
mid=(L+R)/2;
turn_on_off(N,L,mid,1); //Turn on
int actual=tryCombination(temp);
turn_on_off(N,L,mid,0); //Turn off
if(door_changed(i,inicial,actual)) //As door changed, switch have to be in range [L,mid]
R=mid-1;
else
L=mid+1;
}
d[L]=i; //Switch L opens door i
if(inicial==i) //As with all off door was closed, we activate the switch
s[L]=1;
else
s[L]=0; //Door was already open with switch off
temp[L]=s[L];
}
void exploreCave(int N) {
for(int i=0;i<N;i++){
s[i]=-1;
}
for(int i=0;i<N;i++){ //Open all doors
openDoor(N,i);
}
answer(s,d);
}
