#include "cave.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
bool isOpen(int *p, int &k){
int a = tryCombination(p);
if(a==-1 || a>k) return 1;
return 0;
}
void exploreCave(int N) {
int stat[N], door[N], frDoor[N];
for(int i = 0; i < N; i++) stat[i] = -1;
for(int i = 0; i < N; i++){
vi c;
for(int i = 0; i < N; i++){
if(stat[i]==-1) c.push_back(i);
}
int p[N];
for(int i = 0; i < N; i++){
if(stat[i]==-1) p[i] = 0;
else p[i] = stat[i];
}
if(isOpen(p, i)) frDoor[i] = 0;
else frDoor[i] = 1;
int st = 0, end = c.size()-1, mid;
while(st<end){
for(auto x: c) p[x] = frDoor[i]^1;
mid = (st+end)>>1;
for(int j = st; j <= mid; j++){
p[c[j]] = frDoor[i];
}
if(isOpen(p, i)) end = mid;
else st = mid+1;
}
door[c[st]] = i;
stat[c[st]] = frDoor[i];
}
answer(stat, door);
}
