제출 #714986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
714986		Stickfish	Swap (BOI16_swap)	C++17	21 / 100	2 ms	792 KiB

swap

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> dp[MAXN][MAXN];
vector<int> subtr[MAXN];

vector<int> unite_subtr(vector<int> ltr, vector<int> rtr) {
    auto lit = ltr.begin();
    auto rit = rtr.begin();
    vector<int> ans = {-1};
    for (int sz = 1; lit < ltr.end() || rit < rtr.end(); sz *= 2) {
        for (int i = 0; i < sz && lit + i < ltr.end(); ++i)
            ans.push_back(lit[i]);
        for (int i = 0; i < sz && rit + i < rtr.end(); ++i)
            ans.push_back(rit[i]);
        lit += sz;
        rit += sz;
    }
    return ans;
}

signed main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i * 2 + 1 >= n) {
            for (int t = 0; t < n; ++t) dp[i][t] = {t};
            continue;
        }
        if (i * 2 + 2 >= n) {
            for (int t = 0; t < n; ++t) {
                dp[i][t] = {min(t, p[i * 2 + 1]), max(t, p[i * 2 + 1])};
            }
            continue;
        }
        for (int t = 0; t < n; ++t) {
            int lchd = i * 2 + 1;
            int rchd = i * 2 + 2;
            if (t < p[lchd] && t < p[rchd]) {
                dp[i][t] = unite_subtr(dp[lchd][p[lchd]], dp[rchd][p[rchd]]);
                dp[i][t][0] = t;
                continue;
            }
            if (p[lchd] < t && p[lchd] < p[rchd]) {
                dp[i][t] = unite_subtr(dp[lchd][t], dp[rchd][p[rchd]]);
                dp[i][t][0] = p[lchd];
                continue;
            }
            // p[rchd] < t, p[lchd]
            vector<int> dp0 = unite_subtr(dp[lchd][p[lchd]], dp[rchd][t]);
            vector<int> dp1 = unite_subtr(dp[lchd][t], dp[rchd][p[lchd]]);
            dp[i][t] = min(dp0, dp1);
            dp[i][t][0] = p[rchd];
        }
    }
    for (auto x : dp[0][p[0]]) {
        cout << x + 1 << ' ';
    }
    cout << endl;
}

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