#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
int *s, *d;
void exploreCave(int N) {
/* ... */
s = new int[N];
d = new int[N];
vector<int> curin;
for (int i = 0; i < N; i++) {
curin.push_back(i);
}
for (int i = 0; i < N; i++) {
//set all to 0
int cv = 0;
for (int v : curin) {
s[v] = 0;
}
int val = tryCombination(s);
if (val == i) {
cv = 1;
}
// cout << i << " --- " << cv << " " << val << endl;
// cout << " ";
// for (int v : curin) cout << v << " ";
// cout << endl;
int l = 0, r = curin.size()-1;
for (int v : curin) s[v] = cv;
while (l != r) {
int mid = (l + r)/2;
//try doing all from l to r
for (int j = mid+1; j <= r; j++) {
s[curin[j]] = 1-cv;
}
if (tryCombination(s) == i) {
//this means that the righ has the ans
for (int j = mid+1; j <= r; j++) {
s[curin[j]] = cv;
l = mid+1;
}
}
else {
r = mid;
}
}
s[curin[l]] = cv;
d[curin[l]] = i;
curin.erase(curin.begin() + l);
}
answer(s, d);
}
