#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, s[N], d[N], test[N];
bool mark[N];
void exploreCave(int N) {
/* ... */
n = N;
for (int i = 0; i < n; i++) {
s[i] = d[i] = -1;
mark[i] = false;
test[i] = 0;
}
for (int i = 0; i < n; i++) {
vector<int> unknowns;
for (int j = 0; j < n; j++) {
if (!mark[j]) unknowns.push_back(j);
}
for (int unknown : unknowns) {
test[unknown] = 1;
}
int correct = (tryCombination(test) != i);
int l = 0, r = (int)unknowns.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
for (int unknown : unknowns) {
test[unknown] = 1 - correct;
}
for (int j = 0; j <= mid; j++) {
test[unknowns[j]] = correct;
}
if (tryCombination(test) != i) {
r = mid;
}
else {
l = mid + 1;
}
}
int sw = unknowns[l];
test[sw] = correct;
mark[sw] = true;
s[sw] = correct;
d[sw] = i;
}
answer(s, d);
}
