Submission #1226388

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

fun

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

int n, q;
vector<vector<pair<int, int>>> chl, chr;
vector<bool> ll;

vector<int> createFunTour(int N, int Q) {
    n = N;
    q = Q;
    ll.assign(n, false);
    chl.resize(n);
    chr.resize(n);
    for (int i = n-1; i >= 1; i--) {
        int curr = i;
        int dis = 0;
        while (curr > 0) {
            int par = (curr - 1) / 2;
            if (curr % 2) ll[curr] = true;
            if (ll[i]) {
                chl[par].push_back({dis+1, i});
            }
            else chr[par].push_back({dis+1, i});
            dis++;
            curr = par;
        }
    }
    for (int i = 0; i < n; i++) {
        sort(chl[i].begin(), chl[i].end());
        sort(chr[i].begin(), chr[i].end());
    }
    vector<int> perm;
    vector<bool> used(n, false);
    perm.push_back(n-1);
    int curr = n-1;
    used[curr] = true;
    while (perm.size() < n) {
        int mx = 0, goTo = 0;
        int dis = 0;
        while (chl[curr].size() > 0 && used[chl[curr].back().second]) chl[curr].pop_back();
        while (chr[curr].size() > 0 && used[chr[curr].back().second]) chr[curr].pop_back();
        if (!chl[curr].empty()) {
            mx = chl[curr].back().first;
            goTo = chl[curr].back().second;
        }
        if (!chr[curr].empty() && chr[curr].back().first >= mx) {
            mx = chr[curr].back().first;
            goTo = chr[curr].back().second;
        }
        while (curr > 0) {
            int par = (curr - 1) / 2;
            dis++;
            while (chl[par].size() > 0 && used[chl[par].back().second]) chl[par].pop_back();
            while (chr[par].size() > 0 && used[chr[par].back().second]) chr[par].pop_back();
            if (dis >= mx) {
                mx = dis;
                goTo = par;
            }
            if (ll[curr] && !chr[par].empty()) {
                int dis2 = chr[par].back().first + dis;
                if (dis2 >= mx) {
                    goTo = chr[par].back().second;
                    mx = chr[par].back().first + dis;
                }
            }
            else if (!ll[curr] && !chl[par].empty()) {
                int dis2 = chl[par].back().first + dis;
                if (dis2 >= mx) {
                    goTo = chl[par].back().second;
                    mx = chl[par].back().first + dis;
                }
            }
            curr = par;
        }
        perm.push_back(goTo);
        curr = goTo;
        used[goTo] = true;
    }
    return perm;
}

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