Submission #965999

#TimeUsernameProblemLanguageResultExecution timeMemory
965999Darren0724Fun Tour (APIO20_fun)C++17
47 / 100
100 ms18148 KiB
#include "fun.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() const int N=100005; int cntid=0; const int INF=1e9; vector<int> sz(N,1),pa(N),ans,dis(N); priority_queue<pair<int,int>> pq[3]; vector<int> createFunTour(int n, int q) { //int H = hoursRequired(0, N - 1); //int A = attractionsBehind(0, N - 1); int c1=0; int need=(n+1)/2; int mn=INF; for(int i=1;i<n;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); } } vector<vector<int>> dis(r.size()-1,vector<int>(N)); vector<int> vis(N); for(int i=0;i<r.size()-1;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<r.size()-1;j++){ if(dis[j][i]<dis0[i]){ p=j;break; } } if(p==-1)p=r.size()-1; pq[p].push({dis0[i],i}); } cntid=r.size(); int last=-1; for(int i=1;i<n;i++){ pair<int,int> p={-1,-1}; for(int j=0;j<cntid;j++){ if(j==last||pq[j].size()==0)continue; p=max(p,make_pair(pq[j].top().first,j)); } last=p.second; auto [dis1,idx]=pq[p.second].top(); pq[p.second].pop(); ans.push_back(idx); } ans.push_back(c1); /*for(int j:ans){ cout<<j<<' '; } cout<<endl;*/ return ans; }

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<r.size()-1;i++){
      |              ~^~~~~~~~~~~
fun.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j=0;j<r.size()-1;j++){
      |               ~^~~~~~~~~~~
#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...