//Sylwia Sapkowska
#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
void exploreCave(int n) {
vector<bool>fixed(n);
int s[n], t[n], where[n];
for (int i = 0; i<n; i++) s[i] = 0;
for (int i = 1; i<=n; i++){
int l = 0, r = n-1;
int ans = 0;
int curr = tryCombination(s);
debug(i, curr);
if (curr == -1) curr = n;
while (r >= l){
int mid = (l+r)/2;
debug(mid);
for (int j = 0; j<n; j++){
t[j] = s[j];
if (!fixed[j] && j <= mid){
t[j] = 1;
}
}
int get = tryCombination(t);
if (get == -1) get = n;
if ((curr < i && get >= i) || (curr >= i && get < i)){
ans = mid;
r = mid-1;
} else {
l = mid+1;
}
}
debug(i, ans);
fixed[ans] = 1;
where[ans] = i-1;
s[ans] = (curr >= i ? 0 : 1);
}
answer(s, where);
}
