#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n;
void know_i(int* d) {
//d[i] = j significa que el switch i esta conectada a la puerta j.
//a[i] = j. " " j " " i.
int s[n];
int a[n];
for (int i=0; i<n; i++) {
a[d[i]] = i;
s[i] = 0;
}
for (int i=0; i<n; i++) {
s[a[i]] = 1;
int dd = tryCombination(s);
if (dd == i) s[a[i]] = 0;
else s[a[i]] = 1;
}
answer(s, d);
}
void know_comb(int* s) {
int a[n];
for (int i=0; i<n; i++) {
a[i] = s[i];
}
int d[n];
for (int i=0; i<n; i++) {
a[i] = 1-s[i];
int dd = tryCombination(a);
d[i] = dd;
a[i] = s[i];
}
answer(s, d);
}
void exploreCave(int N) {
n = N;
int s[n];
int d[n];
vector<bool> vis(n, false);
for (int i=0; i<n; i++) {
int t;
for (int i=0; i<n; i++) {
if (vis[i]) {
continue;
}
s[i] = 0;
}
int dd = tryCombination(s);
if (dd>i || dd==-1) t=0;
else t=1;
int l=0, r=n-1;
int ans;
while (l <= r) {
int m = (l+r)/2;
for (int i=0; i<=m; i++) {
if (vis[i]) {
continue;
}
s[i] = t;
}
for (int i=m+1; i<n; i++) {
if (vis[i]) {
continue;
}
s[i] = 1-t;
}
dd = tryCombination(s);
if (dd>i || dd==-1) {
r = m-1;
ans = m;
}
else {
l = m+1;
}
}
d[ans] = i;
s[ans] = t;
vis[ans] = true;
}
answer(s, d);
}
