#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
vector<bool> used;
vector<bool> numbers;
vector<int> ans1;
vector<bool> ans2;
bool check = false;
int find_kth(int k, int n, int l, int r) {
if(l == r){
used[l] = true;
ans1[k] = l;
int num[n];
for(int i = 0;i<n;i++)num[i] = numbers[i];
num[l] = 1;
int comb = tryCombination(num);
if(comb > k or comb == -1) {
ans2[k] = 1;
}
else {
ans2[k] = 0;
}
return l;
}
int mid = (l+r)/2;
int num[n];
for(int i = 0;i<n;i++)num[i] = numbers[i];
for(int i = 0;i<=mid;i++) {
if(!used[i]) {
num[i] = !num[i];
}
}
int comb = tryCombination(num);
if((comb>k or comb == -1) and !check) {
return find_kth(k, n, l, mid);
}
else if((comb>k or comb == -1) and check) {
return find_kth(k, n, mid+1, r);
}
else {
return find_kth(k, n, mid+1, r);
}
return l;
}
void exploreCave(int N) {
numbers = ans2 = vector<bool>(N, 0);
used = vector<bool> (N+1, false);
ans1 = vector<int> (N, 0);
for(int i = 0;i<N;i++) {
find_kth(i,N,0,N-1);
}
int a1[N];
int a2[N];
for(int i = 0;i<N;i++) {
a1[i] = ans1[i];
}
for(int i = 0;i<N;i++) {
a2[i] = ans2[i];
}
answer(a2, a1);
}
