// And you curse yourself for things you never done
#include<bits/stdc++.h>
#include "cave.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 5010, mod = 1e9 + 7, inf = 1e9 + 10;
int A[maxn], B[maxn], Tmp[maxn];
void exploreCave(int n){
fill(A, A + n, -1);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
Tmp[j] = (A[j] == -1 ? 1 : B[j]);
bool x = (tryCombination(Tmp) == i);
int l = 0, r = n;
while(r-l > 1){
int mid = (l+r) >> 1;
for(int j = 0; j < n; j++)
Tmp[j] = (A[j] == -1 ? (x ^ (j >= mid)) : B[j]);
if(tryCombination(Tmp) == i)
r = mid;
else
l = mid;
}
A[l] = i, B[l] = !x;
}
answer(B, A);
}
