#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;
}
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 j = 0; j < n; j++) {
if (!mark[j]) test[j] = 1;
}
int correct = (tryCombination(test) != i);
int l = 0, r = (int)unknowns.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
for (int j = 0; j < n; j++) {
if (!mark[j]) test[j] = 1 - correct;
}
for (int i = 0; i < unknowns.size(); i++) {
test[unknowns[i]] = correct;
}
if (tryCombination(test) != i) {
r = mid;
}
else {
l = mid + 1;
}
}
mark[l] = true;
s[l] = correct;
d[l] = i;
}
answer(s, d);
}
