#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <map>
#include <complex>
#include <cmath>
#include <set>
#include "cave.h"
using namespace std;
/*
int tryCombination(bool v[]) {
vector<int> doors;
for (int i = 0; i < n; i++) {
if (v[i] == oracle[i]) {
doors.push_back(door[i]);
}
}
sort(doors.begin(), doors.end());
for (int i = 0; i < doors.size(); i++) {
if (doors[i] != i) {
return i;
}
}
return doors.size();
}
*/
void exploreCave (int n) {
vector<pair<int,bool>> vec;
int c[n]; int arr[n];
for (int i = 0; i < n; i++) {
int a[n];
for (int j = 0; j < n; j++) {
a[j] = true;
}
for (auto& p: vec) a[p.first] = p.second;
bool b = (tryCombination(a) >= i + 1);
int l = 0;
int r = n - 1;
while (l != r) {
int m = (l + r)/2;
for (int j = 0; j < n; j++) a[j] = !b;
for (int j = 0; j <= m; j++) {
a[j] = b;
}
for (auto& p: vec) a[p.first] = p.second;
if (tryCombination(a) >= i + 1) {
r = m;
} else {
l = m + 1;
}
}
arr[l] = i;
vec.emplace_back(l, b);
}
for (auto& p: vec) {
c[p.first] = p.second;
}
answer(c, arr);
}
