Submission #320203

#	Time	Username	Problem	Language	Result	Execution time	Memory
320203		VEGAnn	Fun Tour (APIO20_fun)	C++14	100 / 100	349 ms	20444 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
const int oo = 2e9;
const int N = 100100;
vector<int> ans, chld;
vector<i2> elms[3];
int dst[N];

vector<int> createFunTour(int n, int Q) {
    if (n == 2) return {0, 1};

    int cen = -1, mn = oo, hlf = (n + 1) / 2;

    for (int i = 0; i < n; i++){
        int now = attractionsBehind(0, i);

        if (now < mn && now >= hlf){
            mn = now;
            cen = i;
        }
    }

    chld.clear();

    for (int i = 0; i < n; i++){
        if (i == cen) continue;

        int now = hoursRequired(cen, i);

        dst[i] = now;

        if (now == 1)
            chld.PB(i);
    }

    for (int i = 0; i < n; i++){
        if (i == cen) continue;

        int who = 0;

        for (int it = 1; it < sz(chld); it++){
            int now = hoursRequired(chld[it], i);

            if (now + 1 == dst[i]){
                who = it;
                break;
            }
        }

        elms[who].PB({dst[i], i});
    }

    for (int i = 0; i < sz(chld); i++){
        sort(all(elms[i]));
    }

    if (sz(elms[0]) < sz(elms[1])) swap(elms[0], elms[1]);
    if (sz(chld) == 3 && sz(elms[1]) < sz(elms[2])) swap(elms[1], elms[2]);
    if (sz(elms[0]) < sz(elms[1])) swap(elms[0], elms[1]);

    ans.clear();

    if (sz(chld) == 3 && sz(elms[0]) >= sz(elms[1]) + sz(elms[2])){
        chld.pop_back();

        for (i2 cr : elms[2])
            elms[1].PB(cr);

        sort(all(elms[1]));
    }

    if (sz(chld) == 3){
        int lst = -1;

        while (1){
            int bst = -1, id = -1;

            for (int it = 0; it < 3; it++){
                if (it == lst) continue;

                if (elms[it].back()[0] > bst){
                    bst = elms[it].back()[0];
                    id = it;
                }
            }

            ans.PB(elms[id].back()[1]);
            elms[id].pop_back();

            lst = id;

            if (sz(elms[0]) == sz(elms[1]) + sz(elms[2])) break;
            if (sz(elms[1]) == sz(elms[0]) + sz(elms[2])) break;
            if (sz(elms[2]) == sz(elms[0]) + sz(elms[1])) break;
        }

        int mx = -1, who = -1;

        for (int it = 0; it < 3; it++)
            if (sz(elms[it]) > mx){
                mx = sz(elms[it]);
                who = it;
            }

        int id = who;

        for (int it = 0; it < 3; it++){
            if (it == lst || sz(elms[it]) == 0 || it == who) continue;

            if (elms[it].back()[0] >= dst[ans.back()])
                id = it;
        }

        ans.PB(elms[id].back()[1]);
        elms[id].pop_back();

        swap(elms[0], elms[who]);

        for (i2 cr : elms[2])
            elms[1].PB(cr);

        sort(all(elms[1]));

        if (sz(elms[0]) < sz(elms[1])) swap(elms[1], elms[0]);

        while (sz(elms[1]) > 0){
            ans.PB(elms[0].back()[1]);
            ans.PB(elms[1].back()[1]);

            elms[0].pop_back();
            elms[1].pop_back();
        }

        if (sz(elms[0]) > 0)
            ans.PB(elms[0][0][1]);
    } else {
        while (sz(elms[1]) > 0){
            ans.PB(elms[0].back()[1]);
            ans.PB(elms[1].back()[1]);

            elms[0].pop_back();
            elms[1].pop_back();
        }

        if (sz(elms[0]) > 0)
            ans.PB(elms[0][0][1]);
    }

    ans.PB(cen);

    return ans;
}

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