Submission #1292988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292988		jwpassion1	Swap (BOI16_swap)	C++20	68 / 100	1105 ms	202516 KiB

swap

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int n;
int a[200001];
vector<vector<int>> dptable;
map<pii, int> dp;

void cmpmerge(vector<int>& target, vector<int>& a1, vector<int>& b1, vector<int>& a2, vector<int>& b2) {
    int whi = 0;
    int ai = 0, bi = 0;
    for (int i = 1; ; i <<= 1) {
        if (ai == a1.size()) break;
        int ic = 0;
        while (ic < i && ai < a1.size()) {
            if (whi == 0 && a1[ai] != a2[ai]) {
                if (a1[ai] < a2[ai]) whi = 1;
                else whi = 2;
            }
            if (whi < 2) target.push_back(a1[ai++]);
            else target.push_back(a2[ai++]);
            ic++;
        }
        ic = 0;
        while (ic < i && bi < b1.size()) {
            if (whi == 0 && b1[bi] != b2[bi]) {
                if (b1[bi] < b2[bi]) whi = 1;
                else whi = 2;
            }
            if (whi < 2) target.push_back(b1[bi++]);
            else target.push_back(b2[bi++]);
            ic++;
        }
    }
}

void merge(vector<int>& target, vector<int>& a, vector<int>& b) {
    int ai = 0, bi = 0;
    for (int i = 1; ; i <<= 1) {
        if (ai == a.size()) break;
        int ic = 0;
        while (ic < i && ai < a.size()) {
            target.push_back(a[ai++]);
            ic++;
        }
        ic = 0;
        while (ic < i && bi < b.size()) {
            target.push_back(b[bi++]);
            ic++;
        }
    }
}

void dfs(int node, int val) {
    if (dp.find({node, val}) != dp.end()) return;
    dp[{node, val}] = dptable.size();
    dptable.push_back(vector<int>());
    int l = node << 1, r = node << 1 | 1;
    if (n < l) dptable[dp[{node, val}]] = {val};
    else if (n < r) dptable[dp[{node, val}]] = min(vector<int>{val, a[l]}, vector<int>{a[l], val});
    else {
        if (a[r] <= a[l] && a[r] <= val) {
            int mi = a[l], ma = val;
            if (ma < mi) swap(mi, ma);
            dfs(l, mi);
            dfs(l, ma);
            dfs(r, mi);
            dfs(r, ma);
            dptable[dp[{node, val}]].push_back(a[r]);
            cmpmerge(dptable[dp[{node, val}]], dptable[dp[{l, mi}]], dptable[dp[{r, ma}]], dptable[dp[{l, ma}]], dptable[dp[{r, mi}]]);
        }
        else if (a[l] < val) {
            dfs(l, val);
            dfs(r, a[r]);
            dptable[dp[{node, val}]].push_back(a[l]);
            merge(dptable[dp[{node, val}]], dptable[dp[{l, val}]], dptable[dp[{r, a[r]}]]);
        }
        else {
            dfs(l, a[l]);
            dfs(r, a[r]);
            dptable[dp[{node, val}]].push_back(val);
            merge(dptable[dp[{node, val}]], dptable[dp[{l, a[l]}]], dptable[dp[{r, a[r]}]]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

    dfs(1, a[1]);
    vector<int> ans = dptable[dp[{1, a[1]}]];
    for (int i : ans) cout << i << ' ';
    cout << '\n';
}

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