#include "cave.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 5050;
static int D[N];
static int S[N];
static int rem[N];
static int ask(int l, int r)
{
Loop (i,l,r)
S[rem[i]] = 1;
int ans = tryCombination(S);
Loop (i,l,r)
S[rem[i]] = 0;
if (ans == -1)
ans = N;
return ans;
}
void exploreCave(int N)
{
Loop (i,0,N)
rem[i] = i;
Loop (i,0,N) {
bool open = ask(0, 0) != i;
int l = 0, r = N-1-i;
while (l < r) {
int m = (l + r + 1)/2;
if ((ask(l, m) > i) ^ open)
r = m-1;
else
l = m;
}
D[rem[l]] = i;
S[rem[l]] = !open;
swap(rem[l], rem[N-1-i]);
}
answer(S, D);
}
