제출 #1162391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162391		_callmelucian	Swap (BOI16_swap)	C++17	100 / 100	800 ms	9924 KiB

swap

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

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct vector3D : vector<vector<vector<int>>> {
    vector3D (int x, int y, int z) : vector<vector<vector<int>>>(x, vector<vector<int>>(y, vector<int>(z))) {}
};

const int mn = 4e5 + 5;
int a[mn], n;

vector<int> mergeVector (const vector<int> &a, const vector<int> &b) {
    vector<int> ans;
    int pos = 0;
    for (int sz = 1; pos < max(a.size(), b.size()); pos += sz, sz <<= 1) {
        for (int j = pos; j < pos + sz && j < a.size(); j++) ans.push_back(a[j]);
        for (int j = pos; j < pos + sz && j < b.size(); j++) ans.push_back(b[j]);
    }
    return ans;
}

vector3D solve (int u) {
    if (u > n) return vector3D(19, 2, 0);
    int nodeL = u << 1, nodeR = u << 1 | 1;

    vector3D dp(19, 2, 0);
    vector3D dpL = solve(nodeL), dpR = solve(nodeR);

    for (int climb = 0; (u >> climb) >= 1; climb++) {
        int msk = u >> climb;
        for (int fp = 0; fp <= ((msk & 1) && msk > 1); fp++) {
            vector<int> &state = dp[climb][fp];
            int rootVal = a[msk ^ fp];

            /// case 1: leave everything as it is
            if (rootVal < min(a[nodeL], a[nodeR])) {
                state = mergeVector(dpL[0][0], dpR[0][0]);
                state.insert(state.begin(), rootVal);
            }

            /// case 2: swap with left node
            else if (a[nodeL] < a[nodeR]) {
                state = mergeVector(dpL[climb + 1][fp], dpR[0][0]);
                state.insert(state.begin(), a[nodeL]);
            }

            /// case 3: swap with right node
            else if (a[nodeL] > a[nodeR]) {
                // sub-case 1: leave left node as it is
                vector<int> opt1 = mergeVector(dpL[0][0], dpR[climb + 1][fp]);
                // sub-case 2: swap left node & right node
                vector<int> opt2 = mergeVector(dpL[climb + 1][fp], dpR[0][1]);
                state = min(opt1, opt2);
                state.insert(state.begin(), a[nodeR]);
            }
        }
    }
    return dp;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    fill(a + n + 1, a + 2 * n + 2, INT_MAX);

    vector<int> ans = solve(1)[0][0];
    for (int u : ans) cout << u << " ";

    return 0;
}

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