제출 #1068158

#제출 시각아이디문제언어결과실행 시간메모리
1068158Faisal_Saqib자동 인형 (IOI18_doll)C++17
53 / 100
117 ms17488 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define vll vector<int> #define ll int void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y); vector<int> XP,YP; const int NM=4e5+10; ll cp[NM],final[NM],label=0,father_of_all=-1; vll fast_order(ll n) { if(n==2) return {1,2}; vll ans; ll hn=n/2; for(int i=1;i<=n;i+=2) ans.pb(i); vll hans(hn); vll np=fast_order(n/2); for(int j=0;j<hn;j++) hans[np[j]-1]=ans[j]; ans.clear(); for(auto i:hans) ans.pb(i); for(auto i:hans) ans.pb(i+1); return ans; } void label_it(vll p) { if(p.size()==1)return; vll np; for(int i=0;i<p.size();i+=2) { label++; np.pb(-label); if(p[i]==-NM)// problem p[i]=father_of_all; if(p[i+1]==-NM) p[i+1]=father_of_all; XP.pb(p[i]); YP.pb(p[i+1]); } label_it(np); } void create_circuit(int m, std::vector<int> a) { XP.clear(); YP.clear(); label=0; vector<int> ans(m+1); vector<int> child[m+2]; vector<int> cur; cur.pb(0); for(int j=0;j<a.size();j++) cur.pb(a[j]); cur.pb(0); for(int j=1;j<cur.size();j++) child[cur[j-1]].push_back(cur[j]); int lps=0; for(int i=0;i<=m;i++) { if(child[i].size()==0)continue; if(child[i].size()==1) { ans[i]=child[i][0]; } else { ll pw=1; while(child[i].size()>pw) pw*=2; ll cnt_minus=pw-(ll)child[i].size(); for(int j=0,k=0;j<pw;) { if(cnt_minus>0) { cp[j]=-NM; cp[j+1]=child[i][k]; k++; j+=2; cnt_minus--; } else { cp[j]=child[i][k]; k++; j++; } } // for(int j=0;j<child[i].size();j++) // cp[j]=child[i][j]; // for(int j=child[i].size();j<pw;j++) // cp[j]=-NM; vll order=fast_order(pw); vll fl(pw); for(int j=0;j<pw;j++) { order[j]--; fl[order[j]]=cp[j]; final[order[j]]=cp[j]; } // cout<<"final: "; // for(int j=0;j<pw;j++) // cout<<final[j]<<' '; // cout<<endl; // what switches? father_of_all=-label-pw+1; // pw then label_it(fl); // cout<<"AT "<<i<<' '<<label<<endl;; ans[i]=-label; } /* else if(child[i].size()==2) // solve atmost 2 { // We need s++; ans[i]=-s; x.pb(child[i][0]); y.pb(child[i][1]); } else if(child[i].size()==3) { int s1=s+1; int s2=s+2; int s3=s+3; s+=3; ans[i]=-s1; // s1 x.pb(-s2); y.pb(-s3); //s2 x.pb(-s1); y.pb(child[i][1]); //s3 x.pb(child[i][0]); y.pb(child[i][2]); } else if(child[i].size()==4) { int s1=s+1; int s2=s+2; int s3=s+3; s+=3; ans[i]=-s1; // s1 x.pb(-s2); y.pb(-s3); //s2 x.pb(child[i][0]); y.pb(child[i][2]); //s3 x.pb(child[i][1]); y.pb(child[i][3]); } */ } // cout<<"ans\n"; // for(int i=0;i<=m;i++) // { // cout<<ans[i]<<' '; // } // cout<<endl; // cout<<"xy\n"; // for(int i=0;i<label;i++) // { // cout<<XP[i]<<' '<<YP[i]<<endl; // } answer(ans,XP,YP); }

컴파일 시 표준 에러 (stderr) 메시지

doll.cpp: In function 'void label_it(std::vector<int>)':
doll.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0;i<p.size();i+=2)
      |              ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int j=0;j<a.size();j++)
      |              ~^~~~~~~~~
doll.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int j=1;j<cur.size();j++)
      |              ~^~~~~~~~~~~
doll.cpp:71:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |    while(child[i].size()>pw)
      |          ~~~~~~~~~~~~~~~^~~
doll.cpp:60:6: warning: unused variable 'lps' [-Wunused-variable]
   60 |  int lps=0;
      |      ^~~
#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...