#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
int corrDoor[N];
for (int i =0 ; i < N; i++) corrDoor[i] = -1;
int switches[N];
for (int i = 0; i < N; i++) {
switches[i] = 0;
}
for (int door = 0; door < N; door++) {
bool opened; bool newState;
int left = 0; int right = N-1;
//for (int i = 0; i < N; i++) cerr << switches[i] << " ";
//cerr << '\n';
if (tryCombination(switches) == door) {
opened = false;
}
else opened = true;
while (left < right) {
int mid = (left + right) / 2;
for (int i = left; i <= mid; i++) {
if (corrDoor[i] == -1) {
switches[i] = (switches[i] + 1)%2;
}
}
//for (int i = 0; i < N; i++) cerr << switches[i] << " ";
//cerr << '\n';
if (tryCombination(switches) == door) {
newState = false;
}
else newState = true;
if (newState != opened) {
right = mid;
}
else {
left = mid + 1;
}
opened = newState;
}
corrDoor[left] = door;
if (!opened) switches[left] = (switches[left] + 1) % 2;
}
answer(switches, corrDoor);
}
