#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
void exploreCave(int N) {
int S[N], D[N];
bool fixed[N];
for (int i = 0; i < N; i++) S[i] = 0, D[i] = -1, fixed[i] = false;
int curr;
for (int i = 0; i < N; i++) {
curr = tryCombination(S);
// cerr << i << " : " << curr << '\n';
if (curr == i) {
// 0 i-ci qapini baglayir
// 1 i-ci qapini acir
// qapi hal hazirda baglidir
int low = 0, high = N - 1, mid, best = -1;
while (low <= high) {
mid = (low + high) >> 1;
int lb = low, rb = mid;
// cerr << low << ' ' << mid << ' ' << high << " : ";
for (int j = lb; j <= rb; j++) {
if (!fixed[j]) S[j] = 1;
}
// for (int j = 0; j < N; j++) cerr << S[j] << ' ';
// cerr << '\n';
curr = tryCombination(S);
// cerr << "curr: " << curr << '\n';
if (curr != i || curr == -1) high = mid - 1, best = mid;
else low = mid + 1;
for (int j = lb; j <= rb; j++) if (!fixed[j]) S[j] = 0;
}
// cerr << "Best: " << best << '\n';
D[best] = i, S[best] = 1, fixed[best] = true;
} else {
// 0 i-ci qapini acir
// 1 i-ci qapini baglayir
// qapi hal hazirda aciqdir
int low = 0, high = N - 1, mid, best = -1;
while (low <= high) {
mid = (low + high) >> 1;
int lb = low, rb = mid;
// cerr << low << ' ' << mid << ' ' << high << " : ";
for (int j = lb; j <= rb; j++) {
if (!fixed[j]) S[j] = 1;
}
// for (int j = 0; j < N; j++) cerr << S[j] << ' ';
// cerr << '\n';
curr = tryCombination(S);
// cerr << "curr: " << curr << '\n';
if (curr == i) high = mid - 1, best = mid;
else low = mid + 1;
for (int j = lb; j <= rb; j++) if (!fixed[j]) S[j] = 0;
}
// cerr << "Best: " << best << '\n';
D[best] = i, S[best] = 0, fixed[best] = true;
}
// cerr << "----\n";
}
answer(S, D);
}
/*
5
1 0 1 0 0
1 0 2 4 3
4
1 1 1 0
3 1 0 2
*/
