#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
const int c=5002;
int par[c], t[c];
bool v[c];
/*
int b1;
void answer(int a[], int b[]) {
for (int i=0; i<b1; i++) cout << a[i] << " ";
cout << "\n";
for (int i=0; i<b1; i++) cout << b[i] << " ";
cout << "\n";
return;
}
int tryCombination(int a[]) {
for (int i=0; i<b1; i++) cout << a[i] << " ";
cout << "\n";
for (int i=0; i<b1; i++) if (a[i]==1) return i;
return -1;
//int x; cin >> x;
//return x;
}
*/
void f(int a, int b) {
for (int i=a; i<b; i++) if (!v[i]) t[i]=1-t[i];
}
bool jo(int p) {
int x=tryCombination(t);
if (x==-1) x=1e9;
return x>p;
}
void exploreCave(int n) {
for (int i=0; i<n; i++) {
if (!jo(i)) f(0, n);
int lo=0, hi=n;
while(hi-lo>1) {
int mid=(hi+lo)/2;
f(mid, hi);
if (jo(i)) hi=mid;
else lo=mid, f(mid, hi);
}
par[lo]=i, v[lo]=1;
}
answer(t, par);
}
