#include "cave.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int N;
/*int tryCombination(int S[]){
for (int i=0; i<N; i++) cout<<S[i]<<" ";
cout<<endl;
int a;
cin>>a;
return a;
}
void answer(int S[], int D[]){
for (int i=0; i<N; i++) cout<<S[i]<<" ";
cout<<endl;
for (int i=0; i<N; i++) cout<<D[i]<<" ";
cout<<endl;
return;
}*/
void exploreCave(int N) {
int S[N]={0};
int ans[N];
memset(ans, -1, sizeof ans);
int D[N]={0};
for (int i=0; i<N; i++){
int l=0, r=N-1, m, u;
for (int j=0; j<N; j++){
if (ans[j]!=-1) S[j]=ans[j];
else S[j]=0;
}
int res=tryCombination(S);
m = l + (r-l)/2;
for (int j=0; j<=m; j++){
if (ans[j]!=-1) S[j]=ans[j];
else S[j]=1;
}
int res2=tryCombination(S);
if (res2==res and res==i) {
u=1;
l=m+1;
} else if (res2==res and res!=i) {
u=0;
l=m+1;
} else if (res2!=res and res==i){
u=1;
r=m;
} else{
u=0;
r=m;
}
/*cout << "pre binary search\n";
cout << "ans";
for (int k: ans) cout << ' ' << k;
cout << '\n';
cout << "S";
for (int k: S) cout << ' ' << k;
cout << '\n';
cout << "i " << i << endl;*/
while(l<=r){
m = l + (r-l)/2;
if (l==r) {
D[l]=i;
ans[l]=u;
/*cout << l << ' ' << r << '\n';
cout << "i " << i << endl;
cout << "ans";
for (int k: ans) cout << ' ' << k;
cout << '\n';
cout << "D";
for (int k: D) cout << ' ' << k;
cout << '\n';*/
break;
}
for (int j=l; j<=m; j++){
if (ans[j]!=-1) S[j]=ans[j];
else S[j]=u;
}for (int j=m+1; j<=r; j++){
if (ans[j]!=-1) S[j]=ans[j];
else S[j]= 1-u;
}
res=tryCombination(S);
if (res==i) l=m+1;
else r=m;
/*cout << "i " << i << endl;
cout << l << ' ' << r << '\n';
cout << "ans";
for (int k: ans) cout << ' ' << k;
cout << '\n';
cout << "S";
for (int k: S) cout << ' ' << k;
cout << '\n';*/
}
}answer(ans, D);
}
/*int main(){
cin>>N;
exploreCave(N);
return 0;
}*/
