#include "cave.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
_print(H);
if(sizeof...(T)) cerr<<",";
else cerr<<"\"]";
dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn=5010;
int ans_pos[mxn]; //the door 'switch i' connect to
int ans_dir[mxn]; //correct direction of 'switch i'
int arr[mxn];
int N;
void setall(vector<int> &ar,int val) {
// debug(ar);
for(int i=0;i<N;i++) {
if(ans_dir[i]!=-1) arr[i]=ans_dir[i];
else arr[i]=!val;
}
for(auto e:ar) arr[e]=val;
}
int debug_index=-1;
int solve(vector<int> ar,int correct,int curans) {
if(curans==debug_index) debug(ar),debug(correct);
int sz=ar.size();
if(sz==1) {
// setall(ar,correct);
// int temp=tryCombination(arr);
// assert(temp>curans);
return ar[0];
}
int l=0,r=sz-1;
int mid=(l+r)/2;
vector<int> arL,arR;
for(int i=0;i<=mid;i++) arL.push_back(ar[i]);
for(int i=mid+1;i<sz;i++) arR.push_back(ar[i]);
if(curans==debug_index) {
debug(arL);
debug(arR);
}
setall(arL,correct);
if(curans==debug_index) {
cout<<"[";
for(int i=0;i<N;i++) {
if(i) cout<<",";
cout<<arr[i];
}
cout<<"]"<<endl;
}
int temp=tryCombination(arr);
if(curans==debug_index) debug(temp);
if(temp>curans or temp==-1) return solve(arL,correct,curans);
return solve(arR,correct,curans);
}
void exploreCave(int n) {
N=n;
memset(ans_pos,-1,sizeof(ans_pos));
memset(ans_dir,-1,sizeof(ans_dir));
for(int t=0;t<n;t++) {
vector<int> ar;
for(int i=0;i<n;i++) {
if(ans_pos[i]==-1) {
ar.push_back(i);
}
}
assert(ar.size()==n-t);
setall(ar,1);
int temp=tryCombination(arr);
int correct;
if(temp==t) correct=0;
else correct=1;
if(t==debug_index) debug(correct);
int idx=solve(ar,correct,t);
ans_pos[idx]=t;
ans_dir[idx]=correct;
vector<int> cur_pos(ans_pos,ans_pos+n);
vector<int> cur_dir(ans_dir,ans_dir+n);
// debug(t);
// debug(cur_pos);
// debug(cur_dir);
}
answer(ans_dir,ans_pos);
}
