#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//===================//
// Added libraries //
//===================//
//===================//
//end added libraries//
//===================//
const int MX = 5100;
int n;
int mask[MX], comb[MX], temp[MX];
int con[MX];
int ask(int lb, int ub, bool open) {
RE(i,n) {
if(mask[i]) temp[i] = comb[i];
else temp[i] = (lb <= i && i <= ub) ^ open ^ true;
}
int ret = tryCombination(temp);
if(ret == -1) ret = n;
return ret;
}
void exploreCave(int N) {
n = N;
RE(i,n) mask[i] = 0;
RE(i,n) {
int lb=0, ub=N-1;
bool open = (ask(lb, ub, 1) > i);
while(lb != ub) {
int mid=(lb+ub)/2;
if(ask(lb, mid, open) > i) ub=mid;
else lb=mid+1;
}
mask[lb] = 1;
comb[lb] = open;
con[lb] = i;
}
answer(comb, con);
}
