#include "cave.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
int mod = 1e9+7;
ll modulo(ll a) {
return ((a % mod) + mod) % mod;
}
ll add(ll a, ll b) {
return modulo(a + b);
}
ll mult(ll a, ll b) {
return modulo(a * b);
}
ll binpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b&1) {
res = mult(res, a);
}
a = mult(a, a);
b >>= 1;
}
return res;
}
const int N = 5003;
int known[N], pos[N], door[N];
//~ int _0or1[8] = {0, 1, 1, 0, 1, 0, 1, 1}, sw[8] = {7, 1, 4, 6, 5, 3, 0, 2};
//~ int tryCombination(int pos[]){
//~ int closed = -1;
//~ vector <int> opened(8);
//~ for(int i = 0; i < 8; i++)
//~ if(pos[i] == _0or1[i])
//~ opened[sw[i]]++;
//~ for(int i = 0; i < 8; i++){
//~ if(!opened[i]){
//~ closed = i;
//~ break;
//~ }
//~ }
//~ return closed;
//~ }
//~ void answer(int pos[], int door[]){
//~ int i;
//~ for(i = 0; i < 8; i++) cout << pos[i] << ' ';
//~ cout << endl;
//~ for(i = 0; i < 8; i++) cout << door[i] << ' ';
//~ exit(0);
//~ }
//~ void exploreCave(int n);
//~ int main() {
//~ int n;
//~ cin >> n;
//~ exploreCave(n);
//~ printf("INCORRECT\nYour solution did not call answer().\n");
//~ return 0;
//~ }
void exploreCave(int n) {
for (int i = 0; i < n; i++) {
int way = 0;
for (int j = 0; j < n; j++) {
if (!known[j]) pos[j] = 0;
}
auto res = tryCombination(pos);
if (res == i) {
way = 1;
for (int j = 0; j < n; j++) {
if (!known[j]) pos[j] = 1;
}
}
int l = 0, r = n-1;
while (l < r) {
int mid = (l+r) >> 1;
for (int j = mid+1; j <= r; j++) {
if (!known[j]) pos[j] = 1-way;
}
auto res = tryCombination(pos);
if (res == i) {
for (int j = l; j <= r; j++) {
if (!known[j]) pos[j] = 1-pos[j];
}
l = mid+1;
}
else {
r = mid;
}
}
known[l] = 1;
door[l] = i;
}
answer(pos, door);
}
