#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
#define ll int

void exploreCave(ll n){
    ll S[n], D[n], ans, l, r, ract, res;
    for(int i=0; i<n; i++) S[i]=D[i]=-1;
    for(int i=0; i<n; i++){
        ll act[n];
        for(int j=0; j<n; j++) act[j]=(S[j]!=-1?S[j]:0);
        ans=tryCombination(act);
        if(ans==-1 || ans>i) ract=0;
        else ract=1;
        l=0; r=n-1; res=n;
        while(l<=r){
            ll m=(l+r)/2;
            for(int j=0; j<m; j++){
                if(S[j]!=-1) act[j]=S[j];
                else act[j]=ract^1;
            }
            for(int j=m; j<n; j++){
                if(S[j]!=-1) act[j]=S[j];
                else act[j]=ract;
            }
            ans=tryCombination(act);
            if(ans==-1 || ans>i){
                l=m+1;
                res=m;
            }else r=m-1;
        }
        D[res]=i;
        S[res]=ract;
    }
    answer(S,D);
}