#include "cave.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=5e3;
bool vis[mxN];
int s[mxN], an[mxN];
void change(int i, int j) {
for(int pos=i; pos<=j; pos++) {
if(vis[pos])
continue;
s[pos]=!s[pos];
}
}
void exploreCave(int N) {
for(int i=0; i<N; i++) {
int l=0, r=N-1, final_pos=0;
int sign=tryCombination(s)==i?0:1;
// cout<<"round "<<i<<" sign"<<sign<<" tryCombination"<<tryCombination(s)<<endl;
while(l<=r) {
int mid=(l+r)/2;
change(l, mid);
int res=(tryCombination(s)==i?0:1);
// cout<<"l mid res"<<l<<' '<<mid<<' '<<res<<endl;
change(l, mid);
if(res!=sign)
final_pos=mid, r=mid-1;
else
l=mid+1;
}
// cout<<i<<"final_pos"<<' '<<final_pos<<endl;
vis[final_pos]=1;
an[final_pos]=i;
s[final_pos]=!sign;
}
answer(s, an);
}
