Submission #1139257

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

fun

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

const int N = 100'000;

int n, mark[N + 10];
int ch[2][N + 10], cnt[N + 10];
vector<int> ans;

int getDis(int u, int v) {
    return hoursRequired(u - 1, v - 1);
}

void buildTrie() {
    for (int i = 1; i <= n; i++) {
        int lc = i << 1, rc = i << 1 | 1;
        if (lc <= n)
            ch[0][i] = lc;
        if (rc <= n)
            ch[1][i] = rc;
    }
    for (int i = n; i >= 1; i--)
        cnt[i] = 1 + cnt[ch[0][i]] + cnt[ch[1][i]];
}

int goDown(int u) {
    while (cnt[ch[0][u]] || cnt[ch[1][u]]) {
        if (cnt[ch[0][u]])
            u = ch[0][u];
        else
            u = ch[1][u];
    }
    return u;
}

int calcFirst(int u, int t = 0) {
    int p = (u == 1? 0: calcFirst(u / 2, u % 2));
    if (p != u / 2)
        return p;
    if (cnt[ch[0][u]] && cnt[ch[1][u]])
        return goDown(ch[t ^ 1][u]);
    return u;
}

int getFar(int u) {
    int p = calcFirst(u);
    if (p == u)
        return p / 2;
    return p;
}

void del(int u) {
    while (u) {
        cnt[u]--;
        u /= 2;
    }
}

void solve() {
    buildTrie();
    int u = n;
    for (int i = 1; i <= n; i++) {
        ans.push_back(u);
        //cout << i << ": " << u << endl;
        if (i != n) {
            int last = u;
            u = getFar(u);
            del(last);
        }
    }
}

vector<int> createFunTour(int N, int Q) {
    n = N;
    solve();
    for (int i = 0; i < n; i++)
        ans[i]--;
    return ans;
}

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