Submission #291082

#TimeUsernameProblemLanguageResultExecution timeMemory
291082TadijaSebezFun Tour (APIO20_fun)C++11
10 / 100
1 ms384 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int,int> int SUB(int root,int x){return attractionsBehind(root,x);} int DEP(int root,int x){return hoursRequired(root,x);} const int N=100050; int sz[N],type[N],dist[N]; vector<pii> v[3]; vector<int> createFunTour(int n,int q){ for(int i=0;i<n;i++)sz[i]=SUB(0,i); int cen=0; for(int i=1;i<n;i++)if(sz[i]*2>=n&&sz[i]<sz[cen])cen=i; type[cen]=-1; for(int i=0,cnt=0;i<n;i++){ dist[i]=DEP(cen,i); if(dist[i]==1&&cnt<2&&sz[i]<sz[cen]){ cnt++; for(int j=0;j<n;j++)if(!type[j]){ if(SUB(j,i)*2>n)type[j]=cnt; } } } for(int i=0;i<n;i++)if(type[i]==0)type[i]=3; for(int i=0;i<n;i++)if(i!=cen)v[type[i]-1].pb({dist[i],i}); if(v[0].size()<v[1].size())swap(v[0],v[1]); if(v[0].size()<v[2].size())swap(v[0],v[2]); if(v[1].size()<v[2].size())swap(v[1],v[2]); for(int i=0;i<3;i++)sort(v[i].begin(),v[i].end()); //assert(v[0].size()<=v[1].size()+v[2].size()); int las=-1; vector<int> ans,vals,who; while(max({v[0].size(),v[1].size(),v[2].size()})*2<v[0].size()+v[1].size()+v[2].size()){ int mx=-1,o=-1; for(int i=0;i<3;i++)if(i!=las&&v[i].size()){ if(v[i].back().first>mx)mx=v[i].back().first,o=i; } assert(o!=-1); ans.pb(v[o].back().second); v[o].pop_back(); las=o; vals.pb(mx); who.pb(o); } int mx=0; for(int i=0;i<3;i++)if(v[i].size()>v[mx].size())mx=i; int l=mx==0?1:0,r=mx==2?1:2; if(v[mx].size()==v[l].size()+v[r].size()&&v[mx].size()){ if(who.size()>1){ if(vals[vals.size()-2]<vals[vals.size()-1]){ int o=who[who.size()-2]; ans.pb(v[o].back().second); v[o].pop_back(); } } } if(v[0].size()<v[1].size())swap(v[0],v[1]); if(v[0].size()<v[2].size())swap(v[0],v[2]); if(v[1].size()<v[2].size())swap(v[1],v[2]); //assert(v[0].size()==v[1].size()+v[2].size()); while(v[0].size()){ auto P=[&](int o){ ans.pb(v[o].back().second); v[o].pop_back(); }; P(0); if(v[2].empty()&&v[1].empty())break; if(v[2].empty())P(1); else if(v[1].empty())P(2); else P(v[1].back().first>v[2].back().first?1:2); } ans.pb(cen); return ans; }
#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...