Submission #669029

#	Time	Username	Problem	Language	Result	Execution time	Memory
669029		someone	Fun Tour (APIO20_fun)	C++14	47 / 100	111 ms	16424 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 42;
 
int tmp[N];
 
vector<int> createFunTour(int n, int q) {
    int centroid = 0, dist = 0;
    for(int i = 1; i < n; i++)
        if(n <= 2 * attractionsBehind(0, i)) {
            int d = hoursRequired(0, i);
            if(d > dist) {
                dist = d;
                centroid = i;
            }
        }
    tmp[0] = dist;
    tmp[centroid] = 0;
    for(int i = 1; i < n; i++)
        if(i != centroid)
            tmp[i] = hoursRequired(i, centroid);
    priority_queue<pair<int, int>> pq;
    for(int i = 0; i < n; i++)
        pq.push({tmp[i], i});
    deque<int> pre;
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        int id = pq.top().second;
        pq.pop();
        if(ans.empty())
            ans.push_back(id);
        else {
            int last = ans.back();
            if(tmp[last] + tmp[id] > hoursRequired(last, id))
                pre.push_back(id);
            else {
                ans.push_back(id);
                if(!pre.empty()) {
                    ans.push_back(pre[0]);
                    pre.pop_front();
                }
            }
        }
    }
    while(!pre.empty()) {
        ans.push_back(pre[0]);
        pre.pop_front();
    }
    return ans;
}

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