Submission #986067

#TimeUsernameProblemLanguageResultExecution timeMemory
986067alexddICC (CEOI16_icc)C++17
40 / 100
116 ms640 KiB
#include "icc.h" #include<iostream> #include<vector> #include<algorithm> using namespace std; int n; vector<int> comps[105]; vector<int> ord; int aska[105],askb[105],sa,sb; int wirtz(int poz) { sa=sb=0; for(int i=0;i<=poz;i++) for(auto x:comps[ord[i]]) aska[sa++]=x; for(int i=poz+1;i<ord.size();i++) for(auto x:comps[ord[i]]) askb[sb++]=x; return query(sa,sb,aska,askb); } int boniface(int c1, int poz1, int c2) { sa=sb=0; for(int i=0;i<=poz1;i++) aska[sa++]=comps[c1][i]; for(auto x:comps[c2]) askb[sb++]=x; return query(sa,sb,aska,askb); } void run(int N) { n=N; for(int i=1;i<=n;i++) { ord.push_back(i); comps[i].push_back(i); } for(int pas=1;pas<n;pas++) { // cout<<pas<<" pas incepe\n"; do { random_shuffle(ord.begin(),ord.end()); }while(!wirtz((int)ord.size()/2-1)); // cout<<pas<<" pas intermediar\n"; int st,dr,ans; st=0; dr=(int)ord.size()/2-2; ans=(int)ord.size()/2-1; while(st<=dr) { int mij=(st+dr)/2; if(wirtz(mij)) { ans=mij; dr=mij-1; } else st=mij+1; } int tole = ord[ans]; st=(int)ord.size()/2; dr=(int)ord.size()-2; ans=(int)ord.size()/2-1; while(st<=dr) { int mij=(st+dr)/2; if(wirtz(mij)) { ans=mij; st=mij+1; } else dr=mij-1; } int tori = ord[ans+1]; st=0; dr=(int)comps[tole].size()-2; ans=(int)comps[tole].size()-1; while(st<=dr) { int mij=(st+dr)/2; if(boniface(tole,mij,tori)) { ans=mij; dr=mij-1; } else st=mij+1; } int v1 = comps[tole][ans]; st=0; dr=(int)comps[tori].size()-2; ans=(int)comps[tori].size()-1; while(st<=dr) { int mij=(st+dr)/2; if(boniface(tori,mij,tole)) { ans=mij; dr=mij-1; } else st=mij+1; } int v2 = comps[tori][ans]; setRoad(v1,v2); for(auto x:comps[tori]) comps[tole].push_back(x); comps[tori].clear(); for(int i=0;i<ord.size();i++) { if(ord[i]==tori) { ord.erase(ord.begin()+i); break; } } } } /** 4 1 2 1 3 3 4 */

Compilation message (stderr)

icc.cpp: In function 'int wirtz(int)':
icc.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=poz+1;i<ord.size();i++)
      |                     ~^~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(int i=0;i<ord.size();i++)
      |                     ~^~~~~~~~~~~
#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...