Submission #1173005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173005		OI_Account	Swap (BOI16_swap)	C++20	100 / 100	264 ms	38308 KiB

swap

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

const int N = 200'000;

int n, a[N + 10];
vector<pair<int, int>> vec[N + 10];

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}

void initVec(int u) {
    for (auto [val, id]: vec[u << 1])
        vec[u].push_back({val, 0});
    for (auto [val, id]: vec[u << 1 | 1])
        vec[u].push_back({val, 0});
    vec[u].push_back({a[u << 1], 0});
    if ((u << 1 | 1) <= n)
        vec[u].push_back({a[u << 1 | 1], 0});
    sort(vec[u].begin(), vec[u].end());
    vec[u].resize(unique(vec[u].begin(), vec[u].end()) - vec[u].begin());
}

int getVec(int u, int x) {
    int idx = lower_bound(vec[u].begin(), vec[u].end(), make_pair(x + 1, -1)) - vec[u].begin();
    return vec[u][idx - 1].second;
}

pair<pair<int, int>, int> calcRes(int u, int x) {
    int y = a[u << 1], z = a[u << 1 | 1];
    if ((u << 1 | 1) > n)
        return {{min(x, y), max(x, y)}, 0};
    if (x < y && x < z)
        return {{x, y}, z};
    if (y < x && y < z)
        return {{y, x}, z};
    int a = min(x, y), b = max(x, y);
    int l1 = getVec(u << 1, a);
    int l2 = getVec(u << 1 | 1, a);
    if (l1 <= l2)
        return {{z, a}, b};
    return {{z, b}, a};
}

int getChild(int u, int x) {
    pair<pair<int, int>, int> p = calcRes(u, x);
    return p.first.first == x? 0: (p.first.second == x? 1: 2);
}

int calcVec(int u, int x) {
    int id = getChild(u, x);
    return id == 0? 1: (1 + getVec((u << 1 | (id - 1)), x));
}

void calcVec(int u) {
    if ((u << 1) > n) {
        vec[u].push_back({1, 1});
        return;
    }
    initVec(u);
    for (int i = 0; i < vec[u].size(); i++) {
        int x = vec[u][i].first;
        int y = (i + 1 == (int) vec[u].size()? n + 1: vec[u][i + 1].first);
        if (x + 1 < y)
            vec[u][i].second = calcVec(u, x + 1);
    }
}

void calcVec() {
    for (int i = n; i >= 1; i--)
        calcVec(i);
}

void check(int u) {
    if ((u << 1 | 1) > n) {
        if (a[u << 1] < a[u])
            swap(a[u], a[u << 1]);
        return;
    }
    pair<pair<int, int>, int> p = calcRes(u, a[u]);
    a[u] = p.first.first;
    a[u << 1] = p.first.second;
    a[u << 1 | 1] = p.second;
}

void solve() {
    for (int i = 1; i * 2 <= n; i++)
        check(i);
}

void writeOutput() {
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcVec();
    solve();
    writeOutput();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32