#include "cave.h" #include<bits/stdc++.h> using namespace std; #define MID ((l+r)/2) int n; bool used[10000000] = {}; int state[10000000] = {}; int cnt=0; int query(int l, int r, int sttate){ if(l>=r) return l; int a[n] = {}; for(int i=0;i<l;i++){ if(used[i]) a[i] = state[i]; else a[i] = 1-sttate; } for(int i=l;i<=MID;i++){ if(used[i]) a[i] = state[i]; else a[i] = sttate; } for(int i=MID+1;i<n;i++){ if(used[i]) a[i] = state[i]; else a[i] = 1-sttate; } //for(int i=0;i<n;i++) cout<<a[i]<<" "; //cout<<endl; //cout<<tryCombination(a)<<endl<<endl; int cans = tryCombination(a); if(cans<cnt && cans>=0){ return query(MID+1, r, sttate); } else return query(l, MID, sttate); } void exploreCave(int N) { n = N; int ans[n] = {}; for(int i=0;i<n;i++){ int a[n] = {}; for(int j=0;j<n;j++) a[j] = (used[j] ? state[j] : 0); int correct_state = 1; cnt = i+1; //cout<<"============ "<<cnt<<" ==============\n"; //cout<<"STATE DET: "; //for(int j=0;j<n;j++) cout<<a[j]<<" "; //cout<<endl; //cout<<tryCombination(a)<<endl<<endl; if(tryCombination(a)>=cnt || tryCombination(a)==-1) correct_state=0; //cout<<"STATE: "<<correct_state<<endl; int pos = query(0, n-1, correct_state); ans[pos] = i; state[pos] = correct_state; used[pos] = true; } answer(state, ans); }