#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
//using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define sz(x) (int)x.size()
const char nl = '\n';
void exploreCave(int N) {
int S[N], D[N];
memset(S, 0, sizeof S);
memset(D, -1, sizeof D);
int p = tryCombination(S);
rep(i, 0, N) { // i-1 -cenli hemme gapy acyk
if (p == i) { // yapyk
int l = -1, r = N-1;
while (r-l>1) {
int mid = l+r>>1;
rep(j, 0, mid+1)if (D[j] == -1)S[j] ^= 1;
int a = tryCombination(S);
rep(j, 0, mid+1)if (D[j] == -1)S[j] ^= 1;
if (a != p)r = mid; // acdym
else l = mid;
}
D[r] = p, S[r] ^= 1;
} else { // acyk
int l = -1, r = N-1;
while (r-l>1) {
int mid = l+r>>1;
rep(j, 0, mid+1)if (D[j] == -1)S[j] ^= 1;
int a = tryCombination(S);
rep(j, 0, mid+1)if (D[j] == -1)S[j] ^= 1;
if (a == i)r = mid;
else l = mid;
}
D[r] = i;
}
p = tryCombination(S);
}
answer(S, D);
}
