# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1217018 | lukasuliashvili | Cave (IOI13_cave) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fs first
#define sc second
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=2000005;
int tryCombination(int x[]){
int k;
cin>>k;
return k;
}
signed main(){
int N;
cin>>N;
int s[N],fix[N],ans[N];
for (int i=0; i<N; i++) {
s[i]=0;
fix[i]=0;
ans[i]=0;
}
for (int i=0; i<N; i++) {
int l=0;
int r=N-1;
int last=tryCombination(s);
if (last>=i) {
fix[i]=1;
}
else {
fix[i]=0;
}
while (l<=r) {
int mid = (l+r)/2;
for (int j=0; j<l; j++) {
s[j]=fix[i]^1;
}
for (int j=l; j<=mid; j++) {
s[j]=fix[i];
}
for (int j=mid+1; j<N; j++) {
s[j]=fix[i]^1;
}
int last=tryCombination(s);
if (last<=i){
fix[i]^=1;
l=mid+1;
}
else {
if (l==r) {
ans[i]=l;
}
r=mid-1;
}
}
}
cout<<endl;
cout<<endl;
for(int i=0; i<N;i++){
cout<<ans[i]<<" ";
}
//answer(fix,ans);
}