#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int s[n];
vector<int> switch_of_door(n, -1), correct(n, -1);
for (int door = 0; door < n; door++) {
for (int i = 0; i < n; i++) s[i] = 0;
for (int j = 0; j < door; j++) s[switch_of_door[j]] = correct[j];
int closed_idx = tryCombination(s);
if (closed_idx == door) {
correct[door] = 1;
} else {
correct[door] = 0;
}
int l = 0, r = n; // l <= answer < r
while (r - l > 1) {
int mid = (l + r) / 2;
for (int i = 0; i < n; i++) s[i] = correct[door];
for (int i = l; i < mid; i++) s[i] = !correct[door];
for (int j = 0; j < door; j++) s[switch_of_door[j]] = correct[j];
int closed_idx = tryCombination(s);
if (closed_idx == door) {
r = mid;
} else {
l = mid;
}
}
switch_of_door[door] = l;
}
for (int i = 0; i < n; i++) s[i] = 0;
int d[n];
for (int i = 0; i < n; i++) {
d[switch_of_door[i]] = i;
s[switch_of_door[i]] = correct[i];
}
answer(s, d);
}
