제출 #1188739

#제출 시각아이디문제언어결과실행 시간메모리
1188739Ak_16자동 인형 (IOI18_doll)C++20
84 / 100
46 ms25136 KiB
#include <iostream> #include <vector> #include "doll.h" using namespace std; int bad[1000000]; int po[20]; int n; int inc[1000000]; int l[1000000]; int r[1000000]; int par[1000000]; int swi[1000000]; int swipos[1000000]; int tri[1000000]; int tripos[1000000]; int lf; int scnt; int tcnt; vector<int> c; vector<int> x; vector<int> y; int nx; void rem(int num){ bad[num]=1; if(inc[num]==0){return;} int n1 = num + inc[num]; int n2 = num + 2*inc[num]; rem(n1); rem(n2); } void create_circuit(int m, vector<int> a){ for(int i=0; i<1e6; i++){ bad[i]=0; } n = a.size(); int anew[1000000]; for(int i=0; i<n; i++){ anew[i]=a[i]; } anew[n]=0; po[0]=1; for(int i=1; i<=19; i++){ po[i] = 2*po[i-1]; } c.push_back(a[0]); for(int i=1; i<=m; i++){ c.push_back(-1); } for(int i=0; i<=20; i++){ if(po[i]>=n){ nx=i; break; } } for(int i=0; i<nx; i++){ for(int j=po[i]; j<po[i+1]; j++){ l[j] = j+po[i]; r[j] = j+po[i+1]; par[j+po[i]] = j; par[j+po[i+1]] = j; inc[j] = po[i]; } } for(int i=po[nx]; i<po[nx+1]; i++){ inc[i]=0; } lf=po[nx]-n; int bi[30]; for(int i=19; i>=0; i--){ if(lf>=po[i]){ bi[i]=1; lf -= po[i]; } else { bi[i]=0; } } for(int i=0; i<=nx; i++){ if(bi[nx-i]==1){ int imp; for(int j=po[i]; j<po[i+1]; j++){ if(bad[j]==0){ imp=j; break; } } rem(imp); } } scnt=0; tcnt=0; for(int i=po[nx]; i<po[nx+1]; i++){ if(bad[i]==0){ tcnt++; tri[tcnt]=i; tripos[i]=tcnt; } } for(int i=1; i<po[nx]; i++){ if(bad[i]==0){ scnt++; swi[scnt]=i; swipos[i]=scnt; } } for(int i=1; i<=scnt; i++){ int k = swi[i]; if(bad[l[k]]==1){ x.push_back(-1); } else if(inc[l[k]]==0){ x.push_back(anew[tripos[l[k]]]); } else { x.push_back(-swipos[l[k]]); } if(bad[r[k]]==1){ y.push_back(-1); } else if(inc[r[k]]==0){ y.push_back(anew[tripos[r[k]]]); } else { y.push_back(-swipos[r[k]]); } } answer(c, x, y); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...