#include "cave.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 5e3 + 5;
bool vis[N];
int f(vector < int > a){
int n = (int)a.size();
int s[n];
for(int i = 0; i < n; i++)
s[i] = a[i];
return tryCombination(s);
}
int ok(vector < int > s, bool turn, int l, int r){
for(int i = l; i <= r; i++){
if(vis[i] == false)
s[i] = turn ^ 1;
}
int cur = f(s);
return (cur == -1 ? 1e9 : cur);
}
void exploreCave(int n){
vector < int > s(n, 1);
int x = f(s);
bool turn = (x >= 1);
vector < pair < int , int > > y;
while(y.size() != n){
for(int i = 0; i < n; i++){
if(vis[i] == false){
s[i] = turn;
}
}
x = f(s);
if(x == -1)x = n;
int p = 0;
while(p < n){
int l = p, r = n - 1;
int best = -1;
while(r >= l){
int mid = (l + r) >> 1;
if(ok(s, turn, p, mid) < x){
r = mid - 1;
best = mid;
}
else l = mid + 1;
}
if(best == -1)break;
s[best] = turn ^ 1;
y.push_back({best, f(s)});
vis[best] = true;
s[best] = turn;
p = best + 1;
}
turn ^= 1;
}
sort(y.begin(), y.end());
int e[n], o[n], id1 = 0, id2 = 0;
for(auto [idx, va] : y)e[id1++] = va;
for(auto i : s)o[id2++] = i;
answer(o, e);
}
// C:\Users\Kazim\Downloads\Desktop\cavee
// g++ cave.cpp grader.c -o main
