제출 #282943

#제출 시각아이디문제언어결과실행 시간메모리
282943tinjyu자동 인형 (IOI18_doll)C++14
100 / 100
142 ms13124 KiB
#include <iostream> #include <vector> #include "doll.h" using namespace std; int l[1000005],r[1000005],num[25],d[1000005],b[1000005],x1[1000005],x2[1000005],X[1000005],p=0,Y[1000005]; int qs(int s,int e){ int l=s,r=e,mid=(d[l]+d[r])/2; while(l<=r) { while(d[l]<mid)l++; while(d[r]>mid)r--; if(l<=r) { swap(d[l],d[r]); swap(b[l],b[r]); l++; r--; } } if(s<r)qs(s,r); if(l<e)qs(l,e); return 0; } int find(int x){ if(x==0)return 0; if(x<0)return 1; if(find(l[x])==0 && find(r[x])==0) { return 0; } else if(find(l[x])==0 && find(r[x])==1) { l[x]=0; } return 1; } int solve(int t){ int e=p; if(l[t]>=1) { p++; x1[e]=p; solve(l[t]); } else x1[e]=l[t]; if(r[t]>=1) { p++; x2[e]=p; solve(r[t]); } else x2[e]=r[t]; return 0; } void create_circuit(int M, std::vector<int> A) { int n = A.size(); n++; A[n-1]=1; int t=1; while(t<n) { t*=2; p++; } std::vector<int> C(M + 1); C[0] = -1; for (int i = 1; i <= M; ++i) { C[i] = 1; } num[1]=-1; for(int i=1;i<=t+1;i++) { num[1]++; for(int j=1;j<=p+1;j++) { if(num[j]==2) { num[j]=0; num[j+1]++; } else break; } int q=1; for(int j=p;j>=1;j--) { d[i]+=q*num[j]; q*=2; } } for(int i=t;i>=t-n+1;i--)b[i]=i-1; qs(t-n+1,t); for(int i=1;i<=t-1;i++) { l[i]=(i*2); r[i]=(i*2+1); if(i*2>t-1)l[i]=0; if(i*2+1>t-1)r[i]=0; } for(int i=t-n+1;i<=t;i++) { if(b[i]%2==1)r[(t+b[i])/2]=A[i-(t-n)-1]*-1; else l[(t+b[i])/2]=A[i-(t-n)-1]*-1; } find(1); p=1; solve(1); C[0]=-1; for(int i=0;i<=M;i++)C[i]=-1; std::vector<int> X(p), Y(p); for(int i=0;i<p;i++) { X[i]=x1[i+1]*-1; if(X[i]==0)X[i]=-1; } for(int i=0;i<p;i++) { Y[i]=x2[i+1]*-1; if(Y[i]==0)Y[i]=-1; } Y[p-1]=0; answer(C, X, Y); return ; }
#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...