/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI13_cave
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 300007
#define MAXE 100007
bool debug=false;
void printKey(int s[], int d[], int N) {
cout << "On/off ";
for(int i=0; i<N; i++) cout << s[i] << " ";
cout << endl << "Door ";
for(int i=0; i<N; i++) cout << d[i] << " ";
cout << endl;
}
/*
int tryCombination(int S[]){
int s0[] ={1,1,1,0}, d0[] = {3,1,0,2};
int ok[] ={0,0,0,0};
for(int i=0;i<4;i++)
if(S[i]==s0[i]) ok[d0[i]] = 1;
for(int i=0;i<4;i++)
if(!ok[i]) return i;
return -1;
}
void answer(int s[], int d[]) {
cout << "final answer" << endl;
printKey(s,d,4);
}
*/
#include "cave.h"
void exploreCave(int N) {
int corSet[N],corDoor[N];
if(N==1) { // special case
corDoor[0] = 0; corSet[0] = 1;
if(tryCombination(corSet)==0) corSet[0] = 0;
answer(corSet, corDoor);
}
for(int i=0;i<N;i++) { corSet[i]=0; corDoor[i]=-1;}
for(int cur = 0; cur <N; cur++) {
int l=0, r=N-1;
for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = 0;
int ans = tryCombination(corSet);
int key = 1;
while(l<r) {
// make sure the door is open
if(ans==-1 || ans>cur) {
// door opened, as I wanted
} else {
// flip it to make the door open
for(int i=l; i<=r; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i];
}
// try half of it to close this door
int m = (l+r)/2;
for(int i=l; i<=m; i++) if(corDoor[i] == -1) corSet[i] = !corSet[i];
ans = tryCombination(corSet);
if(ans == cur) {
// successfully closed it. The correct door is in this half
r=m;
key = !corSet[l]; // door closed, so key is the flip
} else {
l=m+1;
key = corSet[l]; // door stays open
}
}
corDoor[l] = cur;
corSet[l] = key;
if(debug) printKey(corSet, corDoor, N);
}
answer(corSet, corDoor);
}
/*
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
exploreCave(4);
if(debug) cout << endl << "EOL" << endl;
}
*/
