제출 #595350

#제출 시각아이디문제언어결과실행 시간메모리
595350mosiashvililuka자동 인형 (IOI18_doll)C++14
85.55 / 100
102 ms22584 KiB
#include<bits/stdc++.h> #include "doll.h" using namespace std; const int N=-400009; int a,b,c,d,e,i,j,ii,jj,zx,xc,f[200009],pi,za,lf[400009],rg[400009],rt,BOlf[400009],BOrg[400009],sw[400009],co,SIZ,l,r; vector <int> C,X,Y,v[200009]; bool chk(int q, int w){ if(q>r||w<l) return 0; else return 1; } void rec(int q, int w, int rr){ int mid=(q+w)/2; if(q==mid){ if(chk(q,mid)==1){ BOlf[rr]=1; lf[rr]=-1; }else{ lf[rr]=-1; } }else{ if(chk(q,mid)==1){ pi++;lf[rr]=pi; rec(q,mid,lf[rr]); }else{ lf[rr]=-1; } } if(mid+1==w){ if(chk(mid+1,w)==1){ BOrg[rr]=1; rg[rr]=-1; }else{ rg[rr]=-1; } }else{ if(chk(mid+1,w)==1){ pi++;rg[rr]=pi; rec(mid+1,w,rg[rr]); }else{ rg[rr]=-1; } } } void dfs(int rr){ if(xc>=SIZ) return; if(sw[rr]==0){ sw[rr]=1; if(lf[rr]!=-1){ dfs(lf[rr]); }else{ if(BOlf[rr]==0){ lf[rr]=rt; }else{ lf[rr]=v[i][xc];xc++; } dfs(rt); } return; } sw[rr]=0; if(rg[rr]!=-1){ dfs(rg[rr]); }else{ if(BOrg[rr]==0){ rg[rr]=rt; }else{ rg[rr]=v[i][xc];xc++; } dfs(rt); } } void create_circuit(int MM, std::vector<int> AA) { a=AA.size();b=MM; for(i=1; i<=a; i++) f[i]=AA[i-1]; C.resize(b+1);pi=0; for(i=1; i<a; i++){ v[f[i]].push_back(f[i+1]); } v[f[a]].push_back(0); C[0]=f[1]; for(i=1; i<=b; i++){ if(v[i].size()==0) continue; if(v[i].size()==1){ C[i]=v[i][0]; continue; } SIZ=v[i].size(); za=1; while(za<SIZ) za*=2; l=za-SIZ+1;r=za; pi++;rt=pi; rec(1,za,rt); //zx=za-SIZ;xc=0; xc=0; dfs(rt); C[i]=-rt; } X.resize(pi);Y.resize(pi); for(i=1; i<=pi; i++){ if(BOlf[i]==1) X[i-1]=lf[i]; else X[i-1]=-lf[i]; if(BOrg[i]==1) Y[i-1]=rg[i]; else Y[i-1]=-rg[i]; } 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...