#include "cave.h"
#include <vector>
#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) {
vector<int> position(N);
bool open = 0;
for (int i = 0; i < N; i++) {
// cout << i << "\n";
int lower = 0, upper = N-1;
int currentFirst = tryCombination(switches);
open = (currentFirst == i);
while (upper - lower > 0) {
int mid = (upper-lower+1)/2;
// printf("Trying %d, %d\n", upper, lower);
flip(lower, lower+mid);
currentFirst = tryCombination(switches);
if (open == (currentFirst == i)) {
lower += mid+1;
} else {
upper = lower+mid;
}
}
done[lower] = true;
door[lower] = i;
}
answer(switches, door);
}
