Submission #1072862

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072862		thinknoexit	Fun Tour (APIO20_fun)	C++17	21 / 100	369 ms	93380 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100100;
int n;
set<pair<int, int>> s[N];
bool ch[N];
vector<int> createFunTour(int _N, int Q) {
    n = _N;
    for (int i = n - 1;i >= 0;i--) {
        s[i].insert({ 0, i });
        if (2 * i + 1 < n) {
            for (auto& [d, j] : s[2 * i + 1]) s[i].insert({ d + 1, j });
        }
        if (2 * i + 2 < n) {
            for (auto& [d, j] : s[2 * i + 2]) s[i].insert({ d + 1, j });
        }
    }
    vector<int> res;
    res.push_back(n - 1);
    while ((int)res.size() < n) {
        int now = res.back();
        ch[now] = 1;
        auto x1 = (--s[now].end());
        int d = 0;
        int mx = x1->first, idx = x1->second;
        s[now].erase({ 0, now });
        while (now != 0) {
            int p = (now - 1) / 2;
            if (ch[p]) break;
            s[p].erase({ ++d, res.back() });
            int dis = d, id = 0;
            if (now == 2 * p + 1) {
                if (s[now + 1].empty()) id = p;
                else {
                    auto x = --s[now + 1].end();
                    dis += x->first, id = x->second;
                }
            }
            else {
                if (s[now - 1].empty()) id = p;
                else {
                    auto x = --s[now - 1].end();
                    dis += x->first, id = x->second;
                }
            }
            if (dis > mx) {
                mx = dis;
                idx = id;
            }
            now = p;
        }
        res.push_back(idx);
    }
    return res;
}

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