#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define sz(x) ll(x.size())
#define all(x) x.begin(), x.end()
#define vt vector
void exploreCave(int N) {
int n = N;
int s[n], d[n]; // swtich combination and connected door.
vector<bool> know(n);
int res = -1;
for(int k=0; k<n; ++k) {
int l = 0, r = n-1;
int q[n];
for(int i=0; i<n; ++i)
q[i] = (know[i] ? s[i] : 0);
int init = tryCombination(q);
int x = init; // if init > k, correct switch lies somewhere
while(l < r) {
int m = (l + r) >> 1;
for(int i=0; i<n; ++i) {
if(know[i])
q[i] = s[i];
else if(i >= l && i <= m)
q[i] = 1;
else
q[i] = 0;
}
x = tryCombination(q);
if(x == -1) x = n;
if((init == k && x > k) || (init > k) && (x <= k)) // door changes state, correct switch on left
r = m;
else
l = m+1;
res = x;
}
// if(k == 1) show(x);
if(init == k)
s[r] = !s[r];
know[r] = true;
d[r] = k;
}
answer(s, d);
}
