#include "cave.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define vi vector<int>
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef short inth;
const int N = 5e3;
const int M = N + 7;
const int MOD = 1e9 + 7;
const ll INF = 1e16 + 17;
bool fx[M];
void fill(int l, int sz, int val, int n, int *sw) {
for (int i = 0; i < n; ++i) {
if (fx[i])
continue;
sw[i] = val ^ 1;
if (l == 0 && sz) {
sw[i] = val;
--sz;
} else {
--l;
}
}
}
void exploreCave(int n) {
int sw[n], door[n];
for (int i = 0; i < n; ++i)
sw[i] = door[i] = 0;
for (int i = 0; i < n; ++i) {
fill(0, n - i, 0, n, sw);
int res = tryCombination(sw);
int appVal = 0;
if (res == i)
appVal = 1;
int l = 0, r = n - i - 1;
while (l != r) {
int mid = (l + r) >> 1;
fill(l, mid - l + 1, appVal, n, sw);
int res = tryCombination(sw);
if (res == i) {
l = mid + 1;
} else {
r = mid;
}
}
for (int j = 0; j < n; ++j) {
if (fx[j])
continue;
if (!l) {
fx[j] = true;
sw[j] = appVal;
door[j] = i;
break;
}
--l;
}
}
answer(sw, door);
}
