Submission #965090

#	Time	Username	Problem	Language	Result	Execution time	Memory
965090		Pannda	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	600 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
using namespace std;

vector<int> createFunTour(int n, int _400000) {
    auto allDistance = [&](int u) {
        vector<int> res(n);
        for (int v = 0; v < n; v++) {
            res[v] = hoursRequired(u, v);
        }
        return res;
    };

    int r = [&]() -> int {
        vector<int> dist = allDistance(0);
        return max_element(dist.begin(), dist.end()) - dist.begin();
    }();
    vector<int> dist = allDistance(r);
    int ir = max_element(dist.begin(), dist.end()) - dist.begin();
    vector<int> idist = allDistance(ir);

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int u, int v) { return dist[u] > dist[v]; });
    vector<int> iorder = order;
    sort(order.begin(), order.end(), [&](int u, int v) { return idist[u] > idist[v]; });

    vector<bool> used(n, false);
    bool toggle = false;
    int u = r;
    vector<int> res;

    for (int i = 0; i < n; i++) {
        res.push_back(u);
        used[u] = true;
        if (toggle == false) {
            int x = u;
            int dx = 0;
            for (int v = 0; v < n; v++) {
                if (used[v]) continue;
                if (dist[v] > dx) {
                    dx = dist[v];
                    x = v;
                }
            }
            u = x;
        } else {
            int x = u;
            int dx = 0;
            for (int v = 0; v < n; v++) {
                if (used[v]) continue;
                if (idist[v] > dx) {
                    dx = idist[v];
                    x = v;
                }
            }
            u = x;
        }
        toggle = !toggle;
    }

    return res;
}

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