# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
963980 | 2024-04-16T06:54:37 Z | vivkostov | Cave (IOI13_cave) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #define "cave.h" using namespace std; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } int n,a[5005],b[5005]; /*int tryCombination(int comb[]) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(b[j]==i) { if(a[j]!=comb[j])return i; } } } return -1; } */ int code[5005],perm[5005]; /*void answer(int code[]) { for(int i=0;i<n;i++) { cout<<code[i]<<" "; } cout<<endl; } */ void exploreCave(int n) //void read() { //cin>>n; for(int i=0;i<n;i++) { //cin>>a[i]; } for(int i=0;i<n;i++) { // in>>b[i]; } /* code[0]=1; code[1]=0; code[2]=1; code[3]=0; */ int h; for(int i=0;i<n;i++) { int g=tryCombination(code); if(g==-1) { answer(code); } if(g>i) { h=0; for(int i=0;i<n;i++) { if(!perm[i]) { code[i]=1; } } } else h=1; int l=0,r=n-1,mi; while(l<=r) { mi=(l+r)/2; for(int j=l;j<=mi;j++) { if(!perm[j])code[j]=h; } g=tryCombination(code); for(int j=l;j<=mi;j++) { if(!perm[j])code[j]=(h+1)%2; } if(g>i||g==-1)r=mi-1; else l=mi+1; } //cout<<l<<endl; perm[l]=1; code[l]=h; for(int i=0;i<n;i++) { //cout<<perm[i]<<" "; } //cout<<endl; for(int i=0;i<n;i++) { if(!perm[i])code[i]=0; //cout<<code[i]<<" "; } //cout<<endl; } answer(code); } int main() { speed(); read(); return 0; }