Submission #561166

#	Time	Username	Problem	Language	Result	Execution time	Memory
561166		piOOE	Fun Tour (APIO20_fun)	C++17	100 / 100	335 ms	20748 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)

vector<int> createFunTour(int n, int q) {
    if (n == 2) {
        return {0, 1};
    }
    vector<int> d(n), sub(n);
    for (int i = 0; i < n; ++i) {
        sub[i] = attractionsBehind(0, i);
    }
    int c = 0;
    for (int i = 1; i < n; ++i) {
        if (sub[i] * 2 > n && sub[i] < sub[c]) {
            c = i;
        }
    }
    vector<int> adj;
    for (int i = 0; i < n; ++i) {
        if (i != c) {
            d[i] = hoursRequired(c, i);
            if (d[i] == 1) {
                adj.push_back(i);
            }
        }
    }
    int sz = int(adj.size());
    vector<priority_queue<array<int, 2>>> v(sz);
    for (int i = 0; i < n; ++i) {
        if (i == c) continue;
        int d0 = hoursRequired(i, adj[0]), d1 = hoursRequired(i, adj[1]);
        if (d0 == d1) {
            v[2].push({d[i], i});
        } else if (d0 < d1) {
            v[0].push({d[i], i});
        } else {
            v[1].push({d[i], i});
        }
    }
    vector<int> ans;
    int last = -1;
    while (ans.size() < n - 1) {
        vector<int> t(sz);
        iota(all(t), 0);
        sort(all(t), [&v](int i, int j) {
            if (v[i].empty()) return false;
            if (v[j].empty()) return true;
            return v[i].top()[0] > v[j].top()[0];
        });
        int a = t[0];
        if (sz > 1 && last == a && !v[t[1]].empty()) {
            a = t[1];
        }
        ans.push_back(v[a].top()[1]);
        v[a].pop();
        last = a;
        if (v[a].empty()) {
            sz -= 1;
            if (a < sz) {
                if (sz == 1) swap(v[1], v[a]);
                else if (sz == 2) swap(v[a], v[2]);
            }
            last = -1;
        }
        sort(all(t), [&v](int i, int j) {
            return v[i].size() > v[j].size();
        });
        if (sz > 2 && v[t[0]].size() > v[t[1]].size() + v[t[2]].size()) {
            int b = t[1] + t[2] - last; //we know that t[1] == last || t[2] == last
            assert(!v[b].empty());
            if (v[b].top()[0] > d[ans.back()]) {
                last = -1;
            }
            if (t[1] > t[2]) swap(t[1], t[2]);
            if (last != -1) last = t[1];
            while (!v[t[2]].empty()) {
                v[t[1]].push(v[t[2]].top());
                v[t[2]].pop();
            }
            if (t[2] == 1) {
                swap(v[1], v[2]);
            }
            sz -= 1;
        }
//        cout << ans.back() << endl;
    }
    ans.push_back(c);
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     while (ans.size() < n - 1) {
      |            ~~~~~~~~~~~^~~~~~~

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