제출 #966537

#제출 시각아이디문제언어결과실행 시간메모리
966537Darren0724즐거운 행로 (APIO20_fun)C++17
66 / 100
2033 ms16952 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define F first #define S second #define all(x) x.begin(),x.end() const int N=100005; int cntid=0; const int INF=1e9; vector<int> ans; priority_queue<pair<int,int>> pq[4]; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); vector<int> createFunTour(int n, int q) { ans.clear(); int c1=0; int need=(n+1)/2; int mn=INF; for(int i=0;i<n-1;i++){ int t=attractionsBehind(0, i); if(t>=need&&t<mn){ mn=t; c1=i; } } vector<int> r; vector<int> dis0(N,0); for(int i=0;i<n;i++){ dis0[i]=hoursRequired(c1,i); if(dis0[i]==1){ r.push_back(i); } } int rsz=r.size()-1; assert(rsz<=2); vector<vector<int>> dis(rsz,vector<int>(N)); vector<int> vis(N); for(int i=0;i<rsz;i++){ for(int j=0;j<n;j++){ dis[i][j]=hoursRequired(r[i],j); } } for(int i=0;i<n;i++){ if(i==c1)continue; int p=-1; for(int j=0;j<rsz;j++){ if(dis[j][i]<dis0[i]){ p=j;break; } } if(p==-1)p=rsz; pq[p].push({dis0[i],i}); } cntid=4; int last=0; int left=n-1; for(int i=1;i<n;i++){ array<int,3> p={-1,-1,-1}; for(int j=0;j<cntid;j++){ if(j==last||pq[j].size()==0)continue; p=max(p,array<int,3>{pq[j].top().first,(int)pq[j].size(),j}); } pair<int,int> mx={-1,-1}; for(int j=0;j<cntid;j++){ mx=max(mx,{(int)pq[j].size(),j}); } if((left-mx.first)<mx.first){ if(last!=mx.S&&(!pq[last].empty()&&!pq[3-last-mx.S].empty())&&pq[last].top().F<pq[3-last-mx.S].top().first){ last=3-last-mx.second; ans.push_back(pq[last].top().second); pq[last].pop(); i++; } if(last==mx.S)last=(last+1)%3; while(!pq[last].empty()){ pq[3-last-mx.S].push(pq[last].top()); pq[last].pop(); } //assert(last!=mx.second); p[2]=mx.second; } last=(p[2]==-1?last:p[2]); //assert(last!=-1&&pq[last].size()>0); auto [dis1,idx]=pq[last].top(); pq[last].pop(); ans.push_back(idx); left--; } ans.push_back(c1); // for(int j:ans){ // cout<<j<<' '; // } // cout<<endl; return ans; } /* 46 100000 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 0 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 0 31 31 32 31 33 32 34 32 35 33 36 33 37 34 38 34 39 35 40 35 41 36 42 36 43 37 44 37 45 */
#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...