#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
int N;
int S[5000], T[5000], O[5000];
//int tryS[5000], tryO[5000], temp[5000];
//int tryCombination(int S[])
//{
// cout << "Try:\n";
// for(int i = 0; i < N; i++) cout << S[i];
// cout << '\n';
// for(int i = 0; i < N; i++) temp[i] = 0;
// for(int i = 0; i < N; i++) if(S[i] == tryS[i]) temp[tryO[i]] = 1;
// for(int i = 0; i < N; i++) if(!temp[i]) return i;
// return -1;
//}
//void answer(int S[], int O[])
//{
// cout << "Answer:\n";
// for(int i = 0; i < N; i++) cout << S[i];
// cout << '\n';
// for(int i = 0; i < N; i++) cout << O[i] << " \n"[i == N];
// return;
//}
void exploreCave(int n)
{
N = n;
vector <int> V(N);
for(int i = 0; i < N; i++) V[i] = i;
for(int i = 0; i < N; i++) O[i] = -1;
auto Try = [&](int l, int r, bool state)
{
for(int i = 0; i < N; i++) T[i] = !state;
for(int i = l; i <= r; i++) T[i] = state;
for(int i = 0; i < N; i++)
{
if(O[i] < 0) continue;
T[i] = S[i];
}
int ret = tryCombination(T);
if(ret < 0) return N;
return ret;
};
for(int i = 0; i < N; i++)
{
// cout << i << ":\n";
// for(int x : V) cout << x << ' ';
// cout << '\n';
int ret, l = 0, r = V.size() - 1, s;
bool state = Try(0, N - 1, 1) > i;
while(l <= r)
{
s = (l + r) >> 1;
if(Try(V[0], V[s], state) <= i) l = s + 1;
else
{
r = s - 1;
ret = V[s];
}
}
S[ret] = state;
O[ret] = i;
for(int j = 0; j < V.size(); j++) if(V[j] == ret) V.erase(V.begin() + j);
}
return answer(S, O);
}
//int main()
//{
// int n;
// cin >> n;
// for(int i = 0; i < n; i++) cin >> tryS[i];
// for(int i = 0; i < n; i++) cin >> tryO[i];
// exploreCave(n);
// return 0;
//}
