#include <bits/stdc++.h>
#include "cave.h"
#define MAXN 5000
using namespace std;
int S[MAXN], D[MAXN], alreadyInCorrectState[MAXN];
void adjustSwitches(int lo, int mid, int hi, int x, int y) {
for (int i = lo; i <= mid; i++)
if (!alreadyInCorrectState[i])
S[i] = x;
for (int i = mid + 1; i <= hi; i++)
if (!alreadyInCorrectState[i])
S[i] = y;
}
int findTheCorrectDoor(int currentSwitch, int lo, int hi) {
if (lo == hi)
return lo;
int mid = (lo + hi) / 2;
adjustSwitches(lo, mid, hi, S[currentSwitch], !S[currentSwitch]);
int ans = tryCombination(S);
if (ans == -1 || ans > mid)
return findTheCorrectDoor(currentSwitch, lo, mid);
else
return findTheCorrectDoor(currentSwitch, mid + 1, hi);
}
void findTheCorrectState(int currentSwitch, int N) {
adjustSwitches(0, (N - 1) / 2, N - 1, 1, 1);
int ans = tryCombination(S);
S[currentSwitch] = ans == -1 || ans > currentSwitch;
alreadyInCorrectState[currentSwitch] = 1;
}
void exploreCave(int N) {
for (int i = 0; i < N; i++) {
findTheCorrectState(i, N);
D[i] = findTheCorrectDoor(i, 0, N - 1);
}
answer(S, D);
}
