# include "cave.h"
# include <bits/stdc++.h>
using namespace std;
/*
int tryCombination(vector < int > S ) {
counts++;
for ( int i = 0; i < n; i++ ) {
if ( S[door[i].first] == door[i].second ) {
continue;
}
return i;
}
return -1;
}
void answer( vector < int > S, vector < int > D ) {
for ( int i = 0; i < n; i++ ) {
int dr = D[i], t = S[i];
cout << S[i] << ' ' << D[i] << '\n';
if ( door[dr].first != i || door[dr].second != t ) {
// cout << "Wrong Answer" << '\n';
// exit(0);
}
}
cout << "Accepted with " << counts << " counts.\n";
exit(0);
}
*/
auto create( int n, int vc[] ) {
for ( int i = 0; i < n; i++ ) {
if ( vc[i] == -1 ) {
vc[i] = 1;
}
}
return vc;
}
int can( int n, int doors[], int mid, int l, int r ) {
int cnt = mid, cntl = 0;
for ( int i = 0; i < n; i++ ) {
if ( doors[i] != -1 ) {
continue;
}
if ( cntl < l ) {
doors[i] = 1;
cntl++;
continue;
}
if ( cnt ) {
doors[i] = 0;
cnt--;
}
else {
doors[i] = 1;
}
}
return tryCombination(doors);
}
int find( int n, int doors[], int l ) {
int cnt = 0;
for ( int i = 0; i < n; i++ ) {
if ( doors[i] != -1 ) {
continue;
}
if ( cnt == l ) {
return i;
}
cnt++;
}
return 0;
}
void exploreCave(int N) {
int n = N;
int doors[N], S[N], D[N];
for ( int i = 0; i < n; i++ ) {
doors[i] = -1;
}
int cnt = N - 1;
for ( int i = 0; i < n; i++ ) {
int fdoor = tryCombination( create(n, doors) );
int ans = 0;
if ( fdoor != i ) {
ans = 1;
}
int l = 0, r = cnt, mid;
while ( l < r ) {
mid = (l + r) / 2;
int x = can( n, doors, mid - l + 1, l, r );
if ( x != i ) {
if ( ans == 0 ) {
r = mid;
}
else {
l = mid + 1;
}
}
else {
if ( ans == 0 ) {
l = mid + 1;
}
else {
r = mid;
}
}
}
int x = find(n, doors, l);
doors[x] = ans;
S[x] = ans;
D[x] = i;
cnt--;
}
answer(S, D);
exit(0);
}
/*
int main()
{
input();
exploreCave(n);
return 0;
}
*/
