#include "cave.h"
#include <iostream>
using namespace std;
int switches[5050];
bool done[5050];
int door[5050];
void flip(int l, int r) {
for (int i = l; i < r; i++) {
if (done[i]) continue;
switches[i] = !switches[i];
}
}
void exploreCave(int N) {
bool open = 0;
for (int i = 0; i < N; i++) {
// cout << i << "\n";
int lower = 0, upper = N;
int currentFirst = tryCombination(switches);
open = (currentFirst == i);
while (upper - lower > 1) {
int mid = (upper-lower+1)/2;
// printf("Trying %d, %d\n", lower, upper);
flip(lower, lower+mid);
currentFirst = tryCombination(switches);
if (open != (currentFirst == i)) {
upper = lower+mid;
} else {
lower += mid;
}
open = (currentFirst == i);
}
// printf("Done with %d, value was %d\n",i,lower);
if (currentFirst == i) switches[lower] = !switches[lower];
done[lower] = true;
door[lower] = i;
}
answer(switches, door);
}
