#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int n) {
int door_of_switch[n], switch_pos_ans[n];
for (int i=0; i<n; i++) switch_pos_ans[i] = -1; // unknown
for (int d=0; d<n; d++) {
int switch_pos[n];
int open_pos = -1;
for (int i=0; i<n; i++) {
if (switch_pos_ans[i] != -1) switch_pos[i] = switch_pos_ans[i];
else switch_pos[i] = 1;
}
int first_closed = tryCombination(switch_pos); // -1 if all open
if (first_closed == -1) first_closed = n;
if (first_closed > d) open_pos = 1;
else open_pos = 0;
int l = 0, r=n-1; int s = -1;
while (l < r) {
int m = (l + r) / 2;
for (int i=0; i<n; i++) {
if (switch_pos_ans[i] != -1) switch_pos[i] = switch_pos_ans[i];
else if (i <= m) switch_pos[i] = open_pos;
else switch_pos[i] = (!open_pos);
}
int first_closed = tryCombination(switch_pos); // -1 if all open
if (first_closed == -1) first_closed = n;
if (first_closed > d) {
s = m;
r = m-1;
} else l = m+1;
}
door_of_switch[s] = d;
switch_pos_ans[s] = open_pos;
}
answer(switch_pos_ans, door_of_switch);
}
