#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
vector<int> left, det;
int *corr = new int[N], *linkto = new int[N];
for (int i = 0; i < N; i++) left.push_back(i);
int *qry = new int[N];
for (int i = 0; i < N; i++) {
fill(qry, qry + N, 0);
for (auto a : det) qry[a] = corr[a];
int x = tryCombination(qry);
if (x == -1) {
x = N;
}
int pos = -1;
if (x > i) {
pos = 0;
} else
pos = 1;
int l = 0, r = left.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
for (int i = l; i <= mid; i++) qry[left[i]] = pos;
for (int i = mid + 1; i <= r; i++) qry[left[i]] = 1 - pos;
x = tryCombination(qry);
if (x == -1) {
x = N;
}
if (x > i) {
r = mid;
} else
l = mid + 1;
}
linkto[left[l]] = i;
corr[left[l]] = pos;
det.push_back(left[l]);
left.erase(left.begin() + l);
}
answer(corr, linkto);
}
