#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
// 0 means default, 1 means switch opposite
vector<int> cur, mapping;
int ask(int lim, int n){
int askVector[n] = {0};
for (int i = 0; i <= lim; i++){
askVector[i] = 1;
}
for (int i = 0; i < n; i++){
if (cur[i] != -1) askVector[i] = cur[i];
}
// for (int i = 0; i < n; i++){
// cout << askVector[i];
// }
// cout << endl;
return tryCombination(askVector);
}
void findKDoor(int k, int n){
// ask to find whether door is open or not, it is open when fi == k
// cout << "For door " << k << " ask for switch 0 to 0" << endl;
int fi = ask(-1, n);
int l = 0, r = n-1;
while(l < r){
int mid = (l + r)/2;
// switches flip does affect, 0 -> mid-1 does contain it
// cout << "For door " << k << " ask for switch 0 to " << mid << endl;
if ((ask(mid, n) == k) != (fi == k)){
r = mid;
}
else{
l = mid + 1;
}
}
// cout << "Found switch " << r << " for door " << k << endl;
// cout << "Should be " << (fi == k) << " to keep open" << endl;
mapping[r] = k;
cur[r] = (fi == k);
}
void exploreCave(int N) {
int n = N;
cur.assign(n, -1);
mapping.assign(n, 0);
for (int k = 0; k < n; k++){
findKDoor(k, n);
}
int s[n], d[n];
for (int i = 0; i < n; i++){
s[i] = cur[i];
d[i] = mapping[i];
}
answer(s, d);
}
