제출 #334052

#제출 시각아이디문제언어결과실행 시간메모리
334052nicholask자동 인형 (IOI18_doll)C++14
53 / 100
144 ms12332 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; /* void answer(vector <int> c,vector <int> x,vector <int> y){ cout<<"C: "; for (auto&i:c) cout<<i<<' '; cout<<endl; cout<<"X: "; for (auto&i:x) cout<<i<<' '; cout<<endl; cout<<"Y: "; for (auto&i:y) cout<<i<<' '; cout<<endl; return; } */ void create_circuit(int m,vector <int> a){ int n=a.size(); int cnt[m+1]={}; for (auto&i:a) cnt[i]++; bool can=1; for (int i=1; i<=m; i++){ if (cnt[i]>4){ can=0; break; } } if (can){ vector <int> c(m+1,0),x,y; c[0]=a[0]; a.push_back(0); vector <int> nxt[m+1]; for (int i=0; i<n; i++) nxt[a[i]].push_back(a[i+1]); int cur=0; for (int i=1; i<=m; i++){ if (nxt[i].size()==1){ c[i]=nxt[i][0]; } else if (nxt[i].size()==2){ cur--; c[i]=cur; x.push_back(nxt[i][0]); y.push_back(nxt[i][1]); } else if (nxt[i].size()==3){ cur--; c[i]=cur; cur--; x.push_back(cur); cur--; y.push_back(cur); x.push_back(c[i]); y.push_back(nxt[i][1]); x.push_back(nxt[i][0]); y.push_back(nxt[i][2]); } else if (nxt[i].size()==4){ cur--; c[i]=cur; cur--; x.push_back(cur); cur--; y.push_back(cur); x.push_back(nxt[i][0]); y.push_back(nxt[i][2]); x.push_back(nxt[i][1]); y.push_back(nxt[i][3]); } } answer(c,x,y); return; } else { vector <int> c(m+1,-1); int ts=1; while (ts<=n){ ts*=2; } ts/=2; vector <int> x(2*ts,-1); vector <int> y(2*ts,-1); for (int i=1; i<ts; i++){ x[i]=-1*(2*i); y[i]=-1*(2*i+1); } for (int i=0; i<n; i++){ int i1=i,cur=1; while (cur<ts){ cur*=2; if (i1&1) cur++; i1/=2; } if (i1%2==0) x[cur]=a[i]; else y[cur]=a[i]; } int cur=1; while (cur<n){ cur*=2; cur++; } y[cur]=0; x.erase(x.begin()); y.erase(y.begin()); answer(c,x,y); return; } } /* int main(){ int n,m; cin>>m>>n; vector <int> a; for (int i=0; i<n; i++){ int t; cin>>t; a.push_back(t); } create_circuit(m,a); } */
#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...