Submission #595078

#TimeUsernameProblemLanguageResultExecution timeMemory
595078mosiashvililukaMechanical Doll (IOI18_doll)C++14
16 / 100
1089 ms20824 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[200009],rg[200009],rt,BOlf[200009],BOrg[200009],sw[200009]; vector <int> C,X,Y,v[200009]; void rec(int q, int w, int rr){ if(w-q+1==2){ lf[rr]=rg[rr]=-1; //BO[rr]=1; return; } pi++; lf[rr]=pi; pi++; rg[rr]=pi; rec(q,(q+w)/2,lf[rr]); rec((q+w)/2+1,w,rg[rr]); } void dfs(int rr){ if(zx==0&&xc>=v[i].size()) return; if(sw[rr]==0){ sw[rr]=1; if(lf[rr]!=-1){ dfs(lf[rr]); }else{ if(zx>0){ zx--;lf[rr]=rt; }else{ lf[rr]=v[i][xc];xc++; BOlf[rr]=1; } dfs(rt); } return; } sw[rr]=0; if(rg[rr]!=-1){ dfs(rg[rr]); }else{ if(zx>0){ zx--;rg[rr]=rt; }else{ rg[rr]=v[i][xc];xc++; BOrg[rr]=1; } 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; } za=1; while(za<v[i].size()) za*=2; pi++;rt=pi; rec(1,za,rt); zx=za-v[i].size();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]; } /*for(i=0; i<=b; i++) cout<<C[i]<<" "; cout<<"\n"; for(i=0; i<X.size(); i++) cout<<X[i]<<" "<<Y[i]<<"\n";*/ answer(C,X,Y); }

Compilation message (stderr)

doll.cpp: In function 'void dfs(int)':
doll.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if(zx==0&&xc>=v[i].size()) return;
      |               ~~^~~~~~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while(za<v[i].size()) za*=2;
      |               ~~^~~~~~~~~~~~
#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...