Submission #560655

#	Time	Username	Problem	Language	Result	Execution time	Memory
560655		piOOE	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	468 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 {
        set<int> L, R;
        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) >> 1]) ++cnt;
            return cnt < 2;
        };
        vector<bool> left(n);
        if (n != 1) {
            left[1] = true;
            for (int i = 1; i < n; ++i) {
                left[i] = (i == 1 || left[(i - 1) >> 1]);
                if (is_leaf(i)) {
                    if (left[i])
                        L.insert(i);
                    else
                        R.insert(i);
                }
            }
        } else {
            return {0};
        }
        vector<int> ans;
        int l = 1;
        int lft = n;
        for (int i = 0; i < n; ++i) {
            if (i == n - 1) {
                ans.push_back(min_element(all(used)) - begin(used));
                break;
            }
            assert(!L.empty() || !R.empty());
            int v;
            if (l) {
                assert(!L.empty());
                v = *L.rbegin();
                ans.push_back(v);
                L.erase(v);
                used[v] = true;
                int cntt = 0;
                if (is_leaf(v * 2 + 2)) {
                    ++cntt;
                    L.insert(v * 2 + 2);
                }
                if (is_leaf(v * 2 + 1)) {
                    ++cntt;
                    L.insert(v * 2 + 1);
                }
                if (v && is_leaf((v - 1) >> 1)) {
                    ++cntt;
                    L.insert((v - 1) >> 1);
                }
                assert(cntt < 2);
            } else {
                if (R.empty()) {
                    int x = *L.rbegin();
                    L.erase(x);
                    R.insert(x);
                    set<int> par;
                    int xx = x;
                    while (xx > 0) {
                        par.insert(xx);
                        xx = (xx - 1) / 2;
                    }
                    while (!L.empty()) {
                        int u = *L.rbegin();
                        int yy = u;
                        bool ok = false;
                        while (yy) {
                            if (par.count(yy)) {
                                ok = true;
                                break;
                            }
                            yy = (yy - 1) / 2;
                        }
                        if (ok) {
                            L.erase(u);
                            R.insert(u);
                        } else {
                            break;
                        }
                    }
                }
                assert(!R.empty());
                v = *R.rbegin();
                used[v] = true;
                ans.push_back(v);
                R.erase(v);
                int cntt = 0;
                if (is_leaf(v * 2 + 2)) {
                    ++cntt;
                    R.insert(v * 2 + 2);
                }
                if (is_leaf(v * 2 + 1)) {
                    ++cntt;
                    R.insert(v * 2 + 1);
                }
                if (v && is_leaf((v - 1) >> 1)) {
                    ++cntt;
                    R.insert((v - 1) >> 1);
                }
                assert(cntt < 2);
            }
            --lft;
            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