Submission #1105726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105726		pan	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	592 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define rep(i,n) for(int i = 0; i< n; i++)
#define pb push_back
#define s second
vector<int> createFunTour(int N, int Q) {
  priority_queue<ii> grps[3];
  vector<int> head;
  int minn=1e9, st=0,dist[100010]; //st is the centroid
  for(int i=1; i<N; i++){
    int nn=attractionsBehind(0,i);
    if(nn>=(N+1)/2 && nn<minn) st=i,minn=nn;
  }
  rep(i,N){
    if(i==st)continue;
    dist[i]=hoursRequired(st,i);
    if(dist[i]==1)head.pb(i);
  }
  rep(i,N){
    if(i==st)continue;
    int x=0;
    while(x<head.size()-1 && dist[i]<hoursRequired(head[x],i)) x++;
    grps[x].push({dist[i],i});
  }
  //cout<<endl;
  vector<int> v;
  rep(i,N-1){
    int x=0;
    if(grps[0].size()<grps[1].size()&&grps[2].size()<grps[1].size())x=1;
    if(grps[0].size()<grps[2].size()&&grps[1].size()<grps[2].size())x=2;
    v.pb(grps[x].top().s);
    grps[x].pop();
  }
  v.pb(st);
  return v;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:24:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     while(x<head.size()-1 && dist[i]<hoursRequired(head[x],i)) x++;
      |           ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34