#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int MAX = 5000;
int n;
bool sure[MAX];
// Correct position of switch (such that the door is open)
int pos[MAX];
// Door the switch is connected to
int door[MAX];
// Find the switch to door d
void find_switch(int d, bool b) {
int lo = 0;
int hi = n;
while (lo < hi) {
int t[n];
copy(pos, pos + n, t);
int mid = (lo + hi) / 2;
for (int i = lo; i <= mid; ++i) {
if (!sure[i]) t[i] = 1;
}
int res = tryCombination(t);
if (b ^ (res == -1 || res > d)) {
hi = mid;
} else {
lo = mid + 1;
}
}
door[lo] = d;
sure[lo] = true;
pos[lo] = !b;
}
void exploreCave(int N) {
n = N;
for (int i = 0; i < n; ++i) {
int cur = tryCombination(pos);
find_switch(i, cur == -1 || cur > i);
}
answer(pos, door);
}
