#include "cave.h"
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define mid ((r+l)>>1)
#define lx (n<<1)
#define rx ((n<<1)|1)
typedef long long ll;
using namespace std;
const int N = 5e3+5;
const long long oo = 1e18 ;
int n , a[N] , b[N] , cur[N] ;
bool vis[N] , is ;
ll bs (ll l , ll r , ll x)
{
if (r == l)
return l ;
for (int i = l ; i<=r ; i++)
{
if (vis[i]) continue ;
cur[i] = !is ;
}
for (int i = l ; i<=mid ; i++)
{
if (vis[i]) continue ;
cur[i] = is ;
}
bool p = (tryCombination(cur) == x) ;
for (int i = l ; i<=mid ; i++)
{
if (vis[i]) continue ;
cur[i] = !is ;
}
if (p)
return bs(mid+1 , r , x) ;
else
return bs(l , mid , x) ;
}
void exploreCave(int N) {
n = N ;
for (int i = 0 ; i<n ; i++)
{
for (int j = 0 ; j < n ; j++)
{
if (vis[j])
{
cur[j] = a[j] ;
continue ;
}
a[j] = 0 ;
}
is = (tryCombination(a) == i) ;
ll j = bs (0 , n-1 , i) ;
a[j] = is ;
b[j] = i ;
vis[j] = true ;
}
answer (a , b) ;
}
