#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int switches[5006];
int sToDoors[5006];
int tryDoors[5006];
void solveDoor(int door, int N){
for (int i = 0; i < N; i++){
if(switches[i] == -1) tryDoors[i] = 0;
else tryDoors[i] = switches[i];
}
int d = tryCombination(tryDoors);
int is_open;
if(d==door) is_open = 0;
else is_open = 1;
int mini = -1;
int maxi = N;
while (maxi - mini > 1){
int mid = (maxi + mini) / 2;
for (int i = 0; i < mid; i++){
if(switches[i] == -1) tryDoors[i] = 1;
else tryDoors[i] = switches[i];
}
int firstDoor = tryCombination(tryDoors);
if (is_open == 1 && firstDoor != door) mini = mid;
else if (is_open == 0 && firstDoor == door) mini = mid;
else maxi = mid;
for (int i = 0; i < mid; i++){
if(switches[i] == -1) tryDoors[i] = 0;
else tryDoors[i] = switches[i];
}
}
sToDoors[mini] = door;
switches[mini] = !is_open;
}
void exploreCave(int N) {
memset(switches, -1, sizeof switches);
for (int i = 0; i < N; i++){
solveDoor(i, N);
}
answer(switches, sToDoors);
}
