Submission #965181

#	Time	Username	Problem	Language	Result	Execution time	Memory
965181		Pannda	Fun Tour (APIO20_fun)	C++17	47 / 100	106 ms	16960 KiB

fun

#include "fun.h"

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

vector<int> createFunTour(int n, int _400000) {
    if (n <= 500) {
        auto findFurthest = [&](int u, set<int> dom) {
            int v = u;
            int dv = 0;
            for (int x : dom) {
                int dx = hoursRequired(u, x);
                if (dx > dv) {
                    v = x;
                    dv = dx;
                }
            }
            return v;
        };
        set<int> rem;
        for (int u = 0; u < n; u++) rem.insert(u);
        int u = findFurthest(0, rem);
        vector<int> res;
        for (int i = 0; i < n; i++) {
            res.push_back(u);
            rem.erase(u);
            u = findFurthest(u, rem);
        }
        return res;
    }

    int centroid = [&]() -> int {
        int res = 0;
        int siz = n;
        for (int v = 0; v < n; v++) {
            int get = attractionsBehind(0, v);
            if (get > n / 2 && get < siz) {
                res = v;
                siz = get;
            }
        }
        return res;
    }();
    vector<int> dist(n);
    for (int u = 0; u < n; u++) dist[u] = hoursRequired(centroid, u);

    int d0 = max_element(dist.begin(), dist.end()) - dist.begin();
    vector<int> dist0(n);
    for (int u = 0; u < n; u++) dist0[u] = hoursRequired(d0, u);

    int d1 = max_element(dist0.begin(), dist0.end()) - dist0.begin();
    vector<int> dist1(n);
    for (int u = 0; u < n; u++) dist1[u] = hoursRequired(d1, u);

    array<vector<int>, 3> dom;
    for (int u = 0; u < n; u++) {
        if (u == centroid) continue;
        if (dist0[u] == dist[u] + dist[d0] && dist1[u] == dist[u] + dist[d1]) {
            dom[2].push_back(u);
        } else if (dist0[u] == dist[u] + dist[d0]) {
            dom[1].push_back(u);
        } else {
            dom[0].push_back(u);
        }
    }
    for (int i = 0; i < 3; i++) {
        sort(dom[i].begin(), dom[i].end(), [&](int u, int v) { return dist[u] > dist[v]; });
    }
    vector<int> order = {0, 1, 2};
    sort(order.begin(), order.end(), [&](int i, int j) { return dom[i].size() < dom[j].size(); });

    vector<int> res = { centroid };

    int last = -1;
    while (dom[order[2]].size() < dom[order[0]].size() + dom[order[1]].size()) {
        int i0;
        int d = n;
        for (int ii = 2; ii >= 0; ii--) {
            int i = order[ii];
            if (i == last) continue;
            if (dom[i].empty()) continue;
            if (dist[res.back()] + dist[dom[i].back()] < d) {
                d = dist[res.back()] + dist[dom[i].back()];
                i0 = i;
            }
        }
        res.push_back(dom[i0].back());
        dom[i0].pop_back();
        last = i0;
        sort(order.begin(), order.end(), [&](int i, int j) { return dom[i].size() < dom[j].size(); });
    }

    bool big = last != order[2];
    while (res.size() < n) {
        int i0;
        if (big) {
            i0 = order[2];
        } else {
            if (dom[order[0]].empty()) i0 = order[1];
            else if (dom[order[1]].empty()) i0 = order[0];
            else i0 = dist[dom[order[0]].back()] < dist[dom[order[1]].back()] ? order[0] : order[1];
        }
        res.push_back(dom[i0].back());
        dom[i0].pop_back();
        big = !big;
    }

    reverse(res.begin(), res.end());
    return res;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     while (res.size() < n) {
      |            ~~~~~~~~~~~^~~
fun.cpp:93:31: warning: 'i0' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |     bool big = last != order[2];
      |                               ^

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