#include "cave.h"
#include<vector>
#include<numeric>
#include<iostream>
using namespace std;
void exploreCave(int N) {
vector<bool> done(N);
int switchs[N];
int doors[N];
for (int i = 0; i < N; i++)
switchs[i] = doors[i] = 0;
auto change = [&]()->void {
for (int i = 0; i < N; i++)
if (!done[i])
switchs[i] ^= 1;
};
auto changed = [&](int mid, int pref)->bool {
for (int i = 0; i <= mid; i++)
if (!done[i])
switchs[i] ^= 1;
int A = tryCombination(switchs);
A = (A == -1 ? N : A);
for (int i = 0; i <= mid; i++)
if (!done[i])
switchs[i] ^= 1;
return A >= pref;
};
for (int i = 0; i < N - 1; i++) {
int pref = tryCombination(switchs);
pref = (pref == -1 ? N : pref);
if (pref > i) {
change();
}
int L = 0, R = N - 1;
while (L < R) {
int mid = (L + R) / 2;
if (changed(mid, i + 1)) {
R = mid;
} else {
L = mid + 1;
}
}
doors[R] = i;
switchs[R] ^= 1;
done[R] = true;
}
for (int i = 0; i < N; i++)
if (!done[i]) {
doors[i] = N - 1;
if (tryCombination(switchs) != -1)
switchs[i] ^= 1;
break;
}
answer(switchs, doors);
}
