Submission #1292986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292986		jwpassion1	Swap (BOI16_swap)	C++20	68 / 100	1103 ms	207984 KiB

swap

#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];
map<pii, vector<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;
    int l = node << 1, r = node << 1 | 1;
    if (n < l) dp[{node, val}] = {val};
    else if (n < r) 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);
            dp[{node, val}].push_back(a[r]);
            cmpmerge(dp[{node, val}], dp[{l, mi}], dp[{r, ma}], dp[{l, ma}], dp[{r, mi}]);
        }
        else if (a[l] < val) {
            dfs(l, val);
            dfs(r, a[r]);
            dp[{node, val}].push_back(a[l]);
            merge(dp[{node, val}], dp[{l, val}], dp[{r, a[r]}]);
        }
        else {
            dfs(l, a[l]);
            dfs(r, a[r]);
            dp[{node, val}].push_back(val);
            merge(dp[{node, val}], dp[{l, a[l]}], dp[{r, a[r]}]);
        }
    }
    //cout << node << ' ' << val << " : \n";
    //for (int i : dp[{node, val}]) cout << i << ' ';
    //cout << '\n';
}

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 = 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