Submission #1055454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055454		AdamGS	Fun Tour (APIO20_fun)	C++17	47 / 100	68 ms	16588 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
vector<int>createFunTour(int n, int q) {
  pair<int,int>mi={n, n};
  rep(i, n) {
    pair<int,int>p={attractionsBehind(0, i), i};
    if(p.st*2>=n) mi=min(mi, p);
  }
  vector<pair<int,int>>P, V[3];
  rep(i, n) P.pb({hoursRequired(mi.nd, i), i});
  sort(all(P));
  for(int i=1; i<P.size(); ++i) {
    int l=0;
    while(l<2 && V[l].size()>0) {
      int x=hoursRequired(P[i].nd, V[l][0].nd);
      if(x==P[i].st-1) break;
      ++l;
    }
    V[l].pb(P[i]);
  }
  vector<int>ans;
  int lst=3;
  rep(i, n-1) {
    pair<int,int>ma={-1, -1};
    rep(j, 3) if(j!=lst && V[j].size()) ma=max(ma, {V[j].back().st, j});
    lst=ma.nd;
    assert(V[ma.nd].size()>0);
    ans.pb(V[ma.nd].back().nd);
    V[ma.nd].pop_back();
  }
  ans.pb(P[0].nd);
  return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:18:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i=1; i<P.size(); ++i) {
      |                ~^~~~~~~~~

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