Submission #366024

#	Time	Username	Problem	Language	Result	Execution time	Memory
366024		tatyam	Fun Tour (APIO20_fun)	C++17	31 / 100	140 ms	15588 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;
    while(a[0].size() || a[1].size() || a[2].size()){
        bool flag = 0;
        for(int i = 0; i < 3; i++) if(a[i].size() > a[(i + 1) % 3].size() + a[(i + 2) % 3].size()){
            ans.push_back(a[i].back());
            a[i].pop_back();
            last = i;
            flag = 1;
            break;
        }
        if(flag) continue;
        const int i = max((last + 1) % 3, (last + 2) % 3, [&](int x, int y) -> bool { if(a[y].empty()) return 0; if(a[x].empty()) return 1; return dist[a[x].back()] < dist[a[y].back()]; });
        ans.push_back(a[i].back());
        a[i].pop_back();
        last = i;
    }
    ans.push_back(cen);
    return ans;
}

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