#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
bool finalized[N];
int CurState[N], connectDoor[N];
for(int i = 0; i < N; i++) {
finalized[i] = false;
CurState[i] = 0;
connectDoor[i] = -1;
}
for(int i = 0; i < N; i++) {
int StateHere[N];
for(int j = 0; j < N; j++) {
StateHere[j] = CurState[j];
}
int maxDoor = tryCombination(StateHere);
/*
mandatory for ith door to be closed
*/
if(maxDoor != i) {
for(int j = 0; j < N; j++) {
if(!finalized[j]) {
StateHere[j] = 1 - StateHere[j];
}
}
}
int l = 0, r = N - 1;
int mid, ans = N;
while(l <= r) {
mid = (l + r) >> 1;
for(int j = l; j <= mid; j++) {
if(!finalized[j]) {
StateHere[j] = 1 - StateHere[j];
}
}
int temp = tryCombination(StateHere);
if(temp != i) { //this brought change, so the door must be within l and mid
ans = mid;
r = mid - 1;
for(int j = l; j <= mid; j++) {
if(!finalized[j]) {
StateHere[j] = 1 - StateHere[j];
}
}
}
else { //door between mid + 1 and r
l = mid + 1;
}
}
finalized[ans] = true;
CurState[ans] = 1 - StateHere[ans];
connectDoor[ans] = i;
}
return answer(CurState, connectDoor);
}
