제출 #1161940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161940		_callmelucian	Swap (BOI16_swap)	C++17	48 / 100	1095 ms	1484 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())

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

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

vector<int> solve (int u) {
    if (u > n) return vector<int>(0);
    int nodeL = u << 1, nodeR = u << 1 | 1;
    vector<int> ans;

    // keep everything as it is
    if (a[u] < min(a[nodeL], a[nodeR])) {
        ans = mergeVector(solve(nodeL), solve(nodeR));
        ans.insert(ans.begin(), a[u]);
    }

    // if left subtree is choosen -> just do it
    else if (a[nodeL] < a[nodeR]) {
        swap(a[u], a[nodeL]);
        ans = mergeVector(solve(nodeL), solve(nodeR));
        ans.insert(ans.begin(), a[u]);
        swap(a[u], a[nodeL]);
    }

    // if right subtree is choosen -> consider 2 cases
    else if (a[nodeL] > a[nodeR]) {
        swap(a[u], a[nodeR]);
        vector<int> candL = mergeVector(solve(nodeL), solve(nodeR));
        candL.insert(candL.begin(), a[u]);

        swap(a[nodeL], a[nodeR]);
        vector<int> candR = mergeVector(solve(nodeL), solve(nodeR));
        candR.insert(candR.begin(), a[u]);

        swap(a[nodeL], a[nodeR]);
        swap(a[u], a[nodeR]);
        ans = min(candL, candR);
    }

    else ans.push_back(a[u]);
    return ans;
}

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

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

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

    return 0;
}

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