Submission #1292983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292983		jwpassion1	Swap (BOI16_swap)	C++20	68 / 100	1102 ms	208884 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];
map<pii, vector<int>> dp;

vector<int> merge(vector<int>& a, vector<int>& b) {
    vector<int> ret;
    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()) {
            ret.push_back(a[ai++]);
            ic++;
        }
        ic = 0;
        while (ic < i && bi < b.size()) {
            ret.push_back(b[bi++]);
            ic++;
        }
    }
    return ret;
}

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 {
        int fro;
        vector<int> tmp;
        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);
            fro = a[r];
            tmp = merge(dp[{l, mi}], dp[{r, ma}]);
            vector<int> tmp1 = merge(dp[{l, ma}], dp[{r, mi}]);
            tmp = min(tmp, tmp1);
        }
        else if (a[l] < val) {
            dfs(l, val);
            dfs(r, a[r]);
            fro = a[l];
            tmp = merge(dp[{l, val}], dp[{r, a[r]}]);
        }
        else {
            dfs(l, a[l]);
            dfs(r, a[r]);
            fro = val;
            tmp = merge(dp[{l, a[l]}], dp[{r, a[r]}]);
        }
        reverse(tmp.begin(), tmp.end());
        tmp.push_back(fro);
        reverse(tmp.begin(), tmp.end());
        dp[{node, val}] = tmp;
    }
    //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