#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int spos[5005], door[5005], ret;
bool cor[5005], prevdopen, dopen;
void exploreCave(int N) {
for (int i = 0; i < N; i++) door[i] = -1;
memset(cor, 0, sizeof cor); //All incorrect
ret = tryCombination(spos);
for (int i = 0; i < N; i++) { //Solve for each door
if (ret == -1 or ret > i) prevdopen = true;
else prevdopen = false;
int upper = N, lower = -1;
while (upper - lower > 1) {
int mid = (upper + lower) / 2;
for (int j = lower + 1; j <= mid; j++) {
if (cor[j]) continue;
spos[j] = !spos[j];
}
ret = tryCombination(spos);
if (ret == -1 or ret > i) dopen = true;
else dopen = false;
if (dopen == prevdopen) lower = mid; //Switch not in this half
else upper = mid;
prevdopen = dopen;
}
door[upper] = i;//Switch is upper
cor[upper] = true;
if (!dopen) { //Guessed which switch but position wrong
spos[upper] = !spos[upper];
ret = tryCombination(spos);
}
}
answer(spos, door);
}
