Submission #965153

#	Time	Username	Problem	Language	Result	Execution time	Memory
965153		Pannda	Fun Tour (APIO20_fun)	C++17	Compilation error	0 ms	0 KiB

fun

#include "fun.h"

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

vector<int> createFunTour(int n, int _400000) {
    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(u, centroid);

    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(); });
    }
    assert(dom[order[2]].size() == dom[order[0]].size() + dom[order[1]].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:69:5: error: expected ';' before 'bool'
   69 |     bool big = last != order[2];
      |     ^~~~
fun.cpp:70:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     while (res.size() < n) {
      |            ~~~~~~~~~~~^~~
fun.cpp:72:13: error: 'big' was not declared in this scope
   72 |         if (big) {
      |             ^~~
fun.cpp:81:9: error: 'big' was not declared in this scope
   81 |         big = !big;
      |         ^~~