#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
#define ask(x) tryCombination(x)
void exploreCave(int n) {
int S[n], D[n], a[n];
bool flag[n]; fill(flag, flag + n, false);
vector<int> left;
for (int i = 0; i < n; i++) left.push_back(i);
fill(a, a + n, 0); // query with a, answer with S
fill(S, S + n, 0);
for (int i = 0; i < n; i++) {
bool f = false, ff = false;
int prev = ask(a);
if (prev == i) f = true;
else f = false;
// cout << prev << "\n";
int l = 0, r = left.size() - 1;
// if (i == 0) cout << prev << "\n";
while (l < r) {
int m = (l + r) >> 1;
for (int j = l; j <= m; j++) a[left[j]] = 1 - a[left[j]];
// if seg of S[i] is closed, it's the other side
prev = ask(a);
if (prev == i) ff = true;
else ff = false;
for (int j = l; j <= m; j++) a[left[j]] = 1 - a[left[j]];
if (f != ff) r = m;
else l = m + 1;
}
D[left[l]] = i; if (f) a[left[l]] ^= 1;
S[left[l]] = f;
left.erase(left.begin() + l);
// cout << S[i] << " " << l << " " << "\n";
// for (int j = 0; j < n; j++) cout << a[j] << " ";
// cout << "\n\n";
}
answer(S, D);
}
