#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 5000;
int N;
int query[MX], open[MX], which[MX];
void exploreCave(int _N) {
N = _N;
memset(open, -1, sizeof(open));
memset(which, -1, sizeof(which));
for (int i=0; i<N; i++) {
// cout << i << " ---" << endl;
for (int j=0; j<N; j++) {
if (open[j] != -1) query[j] = open[j];
else query[j] = 0;
}
int door = tryCombination(query);
int open_first = (door == i);
// for (int i=0; i<N; i++) cout << query[i];
// cout << " => " << door << endl;
// cout << open_first << endl;
vector<int> idx;
for (int j=0; j<N; j++) {
if (open[j] == -1) idx.push_back(j); // cout << j << ' ';
}
// cout << endl;
int k = idx.size();
int l = 0, r = k;
while ((r-l) > 1) {
int m = (l + r) / 2;
// cout << l << ' ' << r << " -- " << m << endl;
for (int j=0; j<l; j++) query[idx[j]] = open_first;
for (int j=l; j<m; j++) query[idx[j]] = !open_first;
for (int j=m; j<k; j++) query[idx[j]] = open_first;
int door = tryCombination(query);
// for (int i=0; i<N; i++) cout << query[i];
// cout << " => " << door << endl;
if (door == i) r = m;
else l = m;
}
// cout << idx[l] << endl << endl;
which[idx[l]] = i;
open[idx[l]] = open_first;
}
answer(open, which);
}
