Submission #367225

#	Time	Username	Problem	Language	Result	Execution time	Memory
367225		tatyam	Fun Tour (APIO20_fun)	C++17	100 / 100	356 ms	21860 KiB

fun

#include <bits/stdc++.h>
using namespace std;
 
int hoursRequired(int X, int Y);
 
int attractionsBehind(int X, int Y);
 
vector<int> createFunTour(int N, int Q) {
    vector<int> siz(N);
    for(int i = 0; i < N; i++) siz[i] = attractionsBehind(0, i);
    auto comp = [&](int x, int y){ if((x * 2 > N) ^ (y * 2 > N)) return x > y; return x < y; };
    const int cen = min_element(siz.begin(), siz.end(), comp) - siz.begin();
    if(*max_element(siz.begin(), siz.end(), comp) * 2 == N){
        const int cen1 = cen, cen2 = max_element(siz.begin(), siz.end(), comp) - siz.begin();
        vector<int> dist1(N), dist2(N);
        for(int i = 0; i < N; i++) dist1[i] = hoursRequired(cen1, i);
        for(int i = 0; i < N; i++) dist2[i] = hoursRequired(cen2, i);
        vector<int> a, b;
        for(int i = 0; i < N; i++) (dist1[i] < dist2[i] ? a : b).push_back(i);
        sort(a.begin(), a.end(), [&](int x, int y){ return dist1[x] > dist1[y]; });
        sort(b.begin(), b.end(), [&](int x, int y){ return dist2[x] > dist2[y]; });
        vector<int> ans;
        for(int i = 0; i < N / 2; i++){
            ans.push_back(a[i]);
            ans.push_back(b[i]);
        }
        return ans;
    }
    vector<int> dist(N);
    for(int i = 0; i < N; i++) dist[i] = hoursRequired(cen, i);
    vector<int> dir;
    for(int i = 0; i < N; i++) if(dist[i] == 1) dir.push_back(i);
    vector<vector<int>> a(3);
    for(int i = 0; i < N; i++) if(i != cen) for(int j = 0; j < 3; j++) if(j == 2 || hoursRequired(dir[j], i) < dist[i]){
        a[j].push_back(i);
        break;
    }
    for(auto& v : a) sort(v.begin(), v.end(), [&](int x, int y){ return dist[x] < dist[y]; });
    sort(a.begin(), a.end(), [](auto& a, auto& b){ return a.size() > b.size(); });
    int last = -1;
    vector<int> ans;
    auto push = [&](int i){
        ans.push_back(a[i].back());
        a[i].pop_back();
        last = i;
    };
    while(a[0].size() && a[1].size() && a[2].size()) [&]{
        for(int i = 0; i < 3; i++) if(a[i].size() > a[(i + 1) % 3].size() + a[(i + 2) % 3].size()){
            push(i);
            return;
        }
        if(all_of(a.begin(), a.end(), [&](auto& v){ return ans.empty() || dist[ans.back()] >= dist[v.back()]; })){
            for(int i = 0; i < 3; i++) if(last != i && a[i].size() == a[(i + 1) % 3].size() + a[(i + 2) % 3].size()){
                push(i);
                return;
            }
        }
        const int i = max((last + 1) % 3, (last + 2) % 3, [&](int x, int y){ return dist[a[x].back()] < dist[a[y].back()]; });
        push(i);
    }();
    while(a[0].size() || a[1].size() || a[2].size()){
        const int i = [&](int x, int y){
            if(a[x].empty()) return y;
            if(a[y].empty()) return x;
            if(dist[a[x].back()] < dist[a[y].back()]) return y;
            return x;
        }((last + 1) % 3, (last + 2) % 3);
        push(i);
    }
    ans.push_back(cen);
    return ans;
}

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