oj.uz

Submission #965235

# Submission time Handle Problem Language Result Execution time Memory
965235 2024-04-18T08:45:59 Z Pannda Fun Tour (APIO20_fun) C++17
47 / 100
 104 ms 15932 KB 
#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(); });
    }

    int first = 0;

    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());
        if (first > 4 && res.size() >= 3) {
            assert(dist[res.end()[-1]] + dist[res.end()[-2]] >= dist[res.end()[-2]] + dist[res.end()[-3]]);
        }
            first++;
        dom[i0].pop_back();
        big = !big;
    }

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 10 ms 524 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 11 ms 600 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 9 ms 560 KB Output is correct
35 Correct 12 ms 524 KB Output is correct
36 Correct 12 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 11 ms 348 KB Output is correct
39 Correct 4 ms 348 KB Output is correct
40 Correct 6 ms 348 KB Output is correct
41 Correct 2 ms 348 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 10 ms 524 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 104 ms 15932 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 3 ms 604 KB Output is correct
22 Correct 5 ms 1284 KB Output is correct
23 Correct 9 ms 2364 KB Output is correct
24 Correct 13 ms 2904 KB Output is correct
25 Correct 57 ms 9084 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 11 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 1 ms 348 KB Tour is not fun
14 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 10 ms 524 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 2 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 11 ms 600 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 9 ms 560 KB Output is correct
35 Correct 12 ms 524 KB Output is correct
36 Correct 12 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 11 ms 348 KB Output is correct
39 Correct 4 ms 348 KB Output is correct
40 Correct 6 ms 348 KB Output is correct
41 Correct 2 ms 348 KB Output is correct
42 Correct 1 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 104 ms 15932 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 2 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 5 ms 1284 KB Output is correct
49 Correct 9 ms 2364 KB Output is correct
50 Correct 13 ms 2904 KB Output is correct
51 Correct 57 ms 9084 KB Output is correct
52 Incorrect 1 ms 348 KB Tour is not fun
53 Halted 0 ms 0 KB -