#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int N = 5e3 + 10;
int n , key[N] , ty[N];
void Find_ty(int id)
{
int ask[n];
for(int i = 0 ; i < n ; i++)
ask[i] = 0;
for(int i = 0 ; i < id ; i++)
ask[key[i]] = ty[i];
int ret = tryCombination(ask);
if(ret == id)
ty[id] = 1;
}
bool Check(int l , int r , int id)
{
int ask[n];
for(int i = 0 ; i < n ; i++)
ask[i] = (ty[id] ^ 1);
for(int i = l ; i < r ; i++)
ask[i] = ty[id];
for(int i = 0 ; i < id ; i++)
ask[key[i]] = ty[i];
int ret = tryCombination(ask);
return (ret != id);
}
void exploreCave(int nn)
{
n = nn;
for(int i = 0 ; i < n ; i++)
{
Find_ty(i);
int low = 0 , high = n;
while(high - low > 1)
{
int mid = (low + high) >> 1;
if(Check(low , mid , i))
high = mid;
else
low = mid;
}
key[i] = low;
}
int A[n] , B[n];
for(int i = 0 ; i < n ; i++)
{
B[key[i]] = i;
A[key[i]] = ty[i];
}
answer(A , B);
}
