Submission #1161882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161882		The_Samurai	Fun Tour (APIO20_fun)	C++20	0 / 100	0 ms	328 KiB

fun

#include "fun.h"
#include "bits/stdc++.h"
using namespace std;

std::vector<int> createFunTour(int n, int q) {
    vector dist(n, vector(n, 0));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        dist[i][j] = hoursRequired(i, j);
    }
    vector<int> pw(20, 1);
    for (int i = 1; i < 20; i++) pw[i] = pw[i - 1] * 2;
    
    auto rec = [&](auto &rec, int n) -> vector<int> {
        if (n == 1) return {0};
        if (n == 2) return {1, 0};
        if (n == 3) return {2, 1, 0};
        vector<int> down, ans;
        int lg = 31 - __builtin_clz(n);
        for (int i = pw[lg] - 1; i < n; i++) down.emplace_back(i);

        // cout << n << ' ' << down.size() << endl;
        if (down.size() > pw[lg - 1]) {
            vector<int> vec1, vec2;
            int others = down.size() - pw[lg - 1];
            for (int i = 0; i < others; i++) {
                vec2.emplace_back(down.back());
                down.pop_back();
            }
            for (int i = 0; i < others; i++) {
                vec1.emplace_back(down.back());
                down.pop_back();
            }
            reverse(vec1.begin(), vec1.end());
            reverse(vec2.begin(), vec2.end());
            for (int i = 0; i < others; i++) {
                ans.emplace_back(vec2.back());
                vec2.pop_back();
                if (i < others - 1) {
                    ans.emplace_back(vec1.back());
                    vec1.pop_back();
                }
            }
            down.emplace_back(vec1.back());
        }
        if (down.empty()) {
            for (int x: rec(rec, pw[lg] - 1)) ans.emplace_back(x);
            return ans;
        }

        vector<int> top;
        for (int i = pw[lg] - pw[lg - 2]; i < pw[lg]; i++) {
            top.emplace_back(i - 1);
        }
        // cout << '\t';
        // for (int x: top) cout << x << ' ';
        // cout << endl;
        if (down.size() + 1 <= top.size()) {
            ans.emplace_back(down.back());
            down.pop_back();
            
            while (!down.empty()) {
                ans.emplace_back(top.back()); 
                top.pop_back();
                ans.emplace_back(down.back());
                down.pop_back();
            }
            auto ans2 = rec(rec, top.empty() ? pw[lg] - pw[lg - 2] - 1 : top.back() + 1);
            for (int x: ans2) ans.emplace_back(x);
            return ans;
        }
        int l = (down.size() - top.size() + 1) / 2 - 1;
        int r = l + top.size() + 1;
        for (int i = 0; i < top.size(); i++) {
            ans.emplace_back(down[i + l + 1]);
            ans.emplace_back(top[top.size() - i - 1]);
        }
        while (l >= 0) {
            if (l + 1 > (int) down.size() - r) {
                ans.emplace_back(down[l--]);
            } else {
                ans.emplace_back(down[r++]);
            }
        }
        auto ans2 = rec(rec, pw[lg] - pw[lg - 2] - 1);
        for (int x: ans2) ans.emplace_back(x);
        return ans;
    };
    auto ans = rec(rec, n);
    // for (int x: ans) cout << x << ' ';
    // cout << endl;
    return ans;
}

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