#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
const int MAXN = 5000;
int config[MAXN], aindex[MAXN], query[MAXN];
int n;
void dnc(int l, int r, int idx, int color);
int find_color(int idx);
void exploreCave(int N)
{
n = N;
memset(config, -1, sizeof(config));
memset(aindex, -1, sizeof(aindex));
for(int i = 0; i < N; ++i)
{
int color = find_color(i);
//cerr << color << '\n';
dnc(0, n-1, i, color);
}
answer(config, aindex);
}
bool is_open(int ans, int tar)
{
if(ans == -1) return true;
return ans > tar;
}
int find_color(int idx)
{
for(int i = 0; i < n; ++i)
{
if(config[i] == -1) query[i] = 1;
else query[i] = config[i];
}
//for(int i = 0; i < n; ++i) cerr << query[i] << ' ';
int i = tryCombination(query);
//cerr << i << '\n';
return is_open(i, idx);
}
void dnc(int l, int r, int idx, int color)
{
if(l == r)
{
config[l] = color;
aindex[l] = idx;
return;
}
int mid = (l + r) / 2;
for(int i = l; i <= r; ++i)
{
if(i <= mid) query[i] = color;
else query[i] = 1 ^ color;
}
for(int i = 0; i < n; ++i)
{
if(config[i] != -1) query[i] = config[i];
}
//for(int i = 0; i < n; ++i) cerr << query[i] << ' ';
//cerr << '\n';
int i = tryCombination(query);
if(is_open(i, idx)) dnc(l, mid, idx, color);
else dnc(mid+1, r, idx, color);
}
