Submission #767152

#TimeUsernameProblemLanguageResultExecution timeMemory
767152DJeniUpMechanical Doll (IOI18_doll)C++17
37 / 100
692 ms34128 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll,ll>pairll; #define pb push_back #define fr first #define sc second ll h,a[400007],b[400007],f[400007],u[400007]; vector<ll>v[200007]; priority_queue<pairll,vector<pairll>, greater<pairll> >p; vector<ll>c,x,y; void create_circuit(int M, std::vector<int> A) { A.pb(0); for(int i=0;i<A.size();i++){ v[0].pb(A[i]); } for(int i=0;i<=M;i++){ if(v[i].size()==0)c.pb(-1); else if(v[i].size()==1)c.pb(v[i][0]); else{ h++; x.pb(-h); y.pb(-h); c.pb(-h); for(int j=0;j<v[i].size();j++){ ll k=-c[i]-1; while(1){ if(f[k]%2==0){ f[k]++; if(x[k]==-k-1){ x[k]=v[i][j]; break; }else if(x[k]<0){ k=-x[k]-1; }else{ h++; f[h-1]=1; x.pb(-h); y.pb(-h); x[h-1]=x[k]; x[k]=-h; k=h-1; } }else{ f[k]++; if(y[k]==-k-1){ y[k]=v[i][j]; break; }else if(y[k]<0){ k=-y[k]-1; }else{ h++; f[h-1]=1; x.pb(-h); y.pb(-h); x[h-1]=y[k]; y[k]=-h; k=h-1; } } } } } } while(1){ ll k=c[0]; ll z=0; ll r=0; for(int i=0;i<h;i++){ f[i]=0; u[i]=0; } while(p.size()>0)p.pop(); ll pr=0; while(k!=0){ r++; pr=k; if(k>0){ k=c[k]; }else{ if(u[-k-1]==0)u[-k-1]=r; if(f[-k-1]%2==0){ p.push({u[-k-1],k}); f[-k-1]++; k=x[-k-1]; }else{ f[-k-1]++; k=y[-k-1]; } } } //cout<<p.back()<<" "<<f[-p.back()-1]<<endl; while(p.size()>0 && f[-p.top().sc-1]%2==0)p.pop(); if(p.size()==0)break; while(p.size()>0){ while(p.size()>0 && f[-p.top().sc-1]%2==0)p.pop(); if(p.size()==0)break; z=p.top().sc; p.pop(); //cout<<z<<endl; if(f[-z-1]%2==0){ break; }else{ if(pr>0)c[pr]=z; else{ if(f[-pr-1]%2==1)x[-pr-1]=z; else y[-pr-1]=z; } k=-z-1; while(1){ pr=-k-1; if(f[k]%2==0){ p.push({u[k],-k-1}); f[k]++; if(x[k]==-k-1){ x[k]=0; break; }else if(x[k]<0){ k=-x[k]-1; }else{ h++; f[h-1]=1; x.pb(-h); y.pb(-h); x[h-1]=x[k]; x[k]=-h; k=h-1; } }else{ f[k]++; if(y[k]==-k-1){ y[k]=0; break; }else if(y[k]<0){ k=-y[k]-1; }else{ h++; f[h-1]=1; x.pb(-h); y.pb(-h); x[h-1]=y[k]; y[k]=-h; k=h-1; } } } } } } //cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl; for(int i=0;i<=M;i++){ // cout<<i<<" "<<c[i]<<endl; } for(int i=0;i<x.size();i++){ //if(x[i]==-i-1)swap(x[i],y[i]); //cout<<-i-1<<" "<<x[i]<<" "<<y[i]<<endl; } if(h>2*A.size()-2)exit(1); answer(c,x,y); return ; }

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<A.size();i++){
      |                 ~^~~~~~~~~
doll.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for(int j=0;j<v[i].size();j++){
      |                         ~^~~~~~~~~~~~
doll.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
doll.cpp:167:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     if(h>2*A.size()-2)exit(1);
      |        ~^~~~~~~~~~~~~
#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...