Submission #367263

#	Time	Username	Problem	Language	Result	Execution time	Memory
367263		tatyam	Fun Tour (APIO20_fun)	C++17	100 / 100	329 ms	21476 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();
    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