#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 5e3+3;
bool isKnown[M];
bool value[M];
int place[M], ivx, N;
void initial(int x)
{
int ask[N] = {};
for(int i=0; i<x; i++)
ask[place[i]] = value[i];
ivx = (tryCombination(ask) == x);
}
void aaa(int x, int l=0, int r=N-1)
{
if(l == r)
{
value[x] = ivx;
place[x] = l;
isKnown[place[x]] = 1;
return;
}
int ask[N];
int mid = (l+r)/2;
for(int i=0; i<x; i++)
ask[place[i]] = value[i];
for(int i=l; i<=mid; i++)
if(!isKnown[i])
ask[i] = ivx;
for(int i=mid+1; i<=r; i++)
if(!isKnown[i])
ask[i] = (!ivx);
int a = tryCombination(ask);
if(a == x)
aaa(x, mid+1, r);
else
aaa(x, l, mid);
}
void exploreCave(int n)
{
N = n;
for(int i=0; i<n; i++)
{
initial(i);
aaa(i);
}
int ans1[n], ans2[n];
for(int i=0; i<n; i++)
ans1[place[i]] = value[i];
for(int i=0; i<n; i++)
ans2[place[i]] = i;
answer(ans1, ans2);
}
