#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int n;
vector<int> found;
vector<int> state;
vector<int> ans;
void exploreCave(int N) {
n = N;
state.resize(n);
ans.resize(n);
found.resize(n);
for (int i = 0; i < n; i++) {
// we gonna find the switch that is connected to i, and the state of that switch
// lets start be finding the state
int s[n];
for (int j = 0; j < n; j++) {
if (found[j]) s[j] = state[j]; // j is the answer to some previous door
else s[j] = 0;
}
int x = tryCombination(s);
int istate = 1;
if ((x == -1) || (x > i)) istate = 0; // i is open with 0
// now we have to find the switch that is connected to i
// binary search: having a group of all switches that could be connected to i
// test half with istate, the other half with !istate
// if the door is open, it is on the first half
// else it is on the second half
// detail: make sure that all the doors before i are already open
vector<int> pos;
for (int j = 0; j < n; j++) if (!found[j]) pos.push_back(j);
while (pos.size() > 1) {
// ok, now just do this
for (int j = 0; j < n; j++) {
if (found[j]) s[j] = state[j]; // j is the answer to some previous door
else s[j] = 0;
}
vector<int> h1, h2;
int t = pos.size();
for (int j = 0; j < (t/2); j++) {
h1.push_back(pos[j]);
s[pos[j]] = istate;
}
for (int j = (t/2); j < t; j++) {
h2.push_back(pos[j]);
s[pos[j]] = (1 - istate); // opposite of istate
}
x = tryCombination(s);
if ((x == -1) || (x > i)) pos = h1;
else pos = h2;
}
found[pos.back()] = 1;
state[pos.back()] = istate;
ans[pos.back()] = i;
}
int s[n];
int d[n];
for (int i = 0; i < n; i++) s[i] = state[i];
for (int i = 0; i < n; i++) d[i] = ans[i];
answer(s, d);
}
