#include "cave.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O4")
#pragma GCC optimize ("fast-math")
#pragma GCC optimize ("unroll-loops")
using namespace std;
/**
#define int long long
#define ll long long
#define all (x) begin(x), end(x)
#define xx first
#define yy second
#define cin fin
#define cout fout
typedef db double;
typedef ldb long double;
typedef vii vector <int>;
typedef pii pair <int, int>;
typedef pai pair <double, double>;
ifstream cin ("cave.in");
ofstream cout ("cave.out");
**/
typedef long long ll;
const int NMAX = 5e3;
ll n;
int usa[NMAX + 1];
int sus[NMAX + 1];
void intoarce (ll val){
for (int i = 0; i <= val; ++ i){
if (usa[i] == -1)
sus[i] ^= 1;
}
}
void init_switches (){
for (int i = 0; i < n; ++ i){
usa[i] = -1;
sus[i] = 0;
}
}
bool solve (int k, int poz){
intoarce(k);
ll rez = tryCombination(sus);
intoarce (k);
return rez == poz;
}
void exploreCave (int N){
n = N;
init_switches();
for (int i = 0; i < n; ++ i){
ll cur = tryCombination(sus);
if (cur == i){
intoarce (n - 1);
}
ll st = 0;
ll dr = n - 1;
ll Answer = -1;
ll mijl;
while (st <= dr){
mijl = (st + dr) >> 1;
if (solve(mijl, i)){
Answer = mijl;
dr = mijl - 1;
}
else
st = mijl + 1;
}
usa[Answer] = i;
}
answer (sus, usa);
}
