Submission #560634

#	Time	Username	Problem	Language	Result	Execution time	Memory
560634		piOOE	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	212 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

vector<int> createFunTour(int n, int q) {
    const int infI = 1e9 + 7;
    if (n <= 0) {
        vector<vector<int>> dist(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                dist[i][j] = dist[j][i] = hoursRequired(i, j);
            }
        }
        int j = 0;
        pair<int, int> mxx = {-infI, -infI};
        for (; j < n; ++j) {
            mxx = max(mxx, make_pair(dist[j][0], j));
        }
        j = mxx.second;
        vector<int> ans;
        vector<bool> used(n);
        int lst = infI;
        for (int k = 0; k < n; ++k) {
            ans.push_back(j);
            used[j] = true;
            pair<int, int> mx = {-infI, -infI};
            for (int z = 0; z < n; ++z) {
                if (!used[z] && dist[j][z] <= lst) {
                    mx = max(mx, make_pair(dist[j][z], z));
                }
            }
            if (mx.first == -infI) {
                break;
            }
            lst = mx.first;
            j = mx.second;
        }
        if (ans.size() == n) {
            return ans;
        }
        assert(false);
        return {};
    } else {
        deque<int> leaves;
        vector<bool> used(n);
        auto is_leaf = [&used, &n](int x) {
            if (x >= n || used[x]) return false;
            int cnt = 0;
            if (x * 2 + 1 < n && !used[x * 2 + 1]) ++cnt;
            if (x * 2 + 2 < n && !used[x * 2 + 2]) ++cnt;
            if (x && !used[x >> 1]) ++cnt;
            return cnt < 2;
        };
        for (int i = 0; i < n; ++i) {
            if (is_leaf(i))
                leaves.push_back(i);
        }
        vector<int> ans;
        int l = 0;
        for (int i = 0; i < n; ++i) {
            assert(!leaves.empty());
            if (l) {
                ans.push_back(*leaves.begin());
                int v = *leaves.begin();
                used[v] = true;
                leaves.pop_front();
                int cntt = 0;
                if (is_leaf(v * 2 + 2)) {
                    ++cntt;
                    leaves.push_front(v * 2 + 2);
                }
                if (is_leaf(v * 2 + 1)) {
                    ++cntt;
                    leaves.push_front(v * 2 + 1);
                }
                if (v && is_leaf((v - 1) >> 1)) {
                    ++cntt;
                    leaves.push_front((v - 1) >> 1);
                }
                assert(cntt < 2);
            } else {
                ans.push_back(*prev(leaves.end()));
                int v = *prev(leaves.end());
                used[v] = true;
                leaves.pop_back();
                int cntt = 0;
                if (is_leaf(v * 2 + 2)) {
                    ++cntt;
                    leaves.push_back(v * 2 + 2);
                }
                if (is_leaf(v * 2 + 1)) {
                    ++cntt;
                    leaves.push_back(v * 2 + 1);
                }
                if (v && is_leaf((v - 1) >> 1)) {
                    ++cntt;
                    leaves.push_back((v - 1) >> 1);
                }
                assert(cntt < 2);
            }
            l ^= 1;
        }
        return ans;
    }
}

Compilation message (stderr)

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

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