#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
#define For(i, a) for (int i=0; i<(a); i++)
#define Ford(i,a) for (int i = (a); i >= 0; i--)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 5001; //check the limits, dummy
int cur, m[MX], r[MX];
void exploreCave(int n){
For(i,n)m[i]=-1;
int tmp[n];For(i,n)tmp[i]=0;
while(cur!=n){//do each door
For(i,n)tmp[i]=(m[i]==-1?0:r[i]);
int tmp3=tryCombination(tmp);
bool c=(tmp3==cur);//true if cur is closed
int l=0, r=n-cur-1;
while(l!=r){//find which switch corresponds to which door
int tmp2=0;
for(int j=0;j<=r;j++){
while(m[tmp2]!=-1)tmp2++;
if(j>=l){
if(j<=(l+r)/2)tmp[tmp2]=1;
else tmp[tmp2]=0;
}
tmp2++;
}
if(c^(tryCombination(tmp)>cur))r=(l+r)/2;// co or oc
else l=(l+r)/2+1;
}
m[l]=cur;
cur++;
}
int ret1[n];
int ret2[n];
For(i,n){
ret1[i]=m[i];ret2[i]=r[i];
}
answer(ret1,ret2);
}
//int main() {
// ios_base::sync_with_stdio(0); cin.tie(0);
//
// int T; cin >> T;
// while(T--) {
//
// }
//
// return 0;
//}
