제출 #702665

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702665		finn__	Swap (BOI16_swap)	C++17	68 / 100	704 ms	262144 KiB

swap

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

#define N 200001

map<unsigned, vector<unsigned>> dp[N];
unsigned y[N];

vector<unsigned> merge_subtrees(unsigned f, vector<unsigned> const &a, vector<unsigned> const &b)
{
    vector<unsigned> c = {f};
    size_t k = 0;
    for (size_t i = 1; k < a.size(); i <<= 1)
    {
        for (size_t j = k; j < a.size() && j < k + i; j++)
            c.push_back(a[j]);
        for (size_t j = k; j < b.size() && j < k + i; j++)
            c.push_back(b[j]);
        k += i;
    }
    return c;
}

void lexicographically_smallest(size_t n, unsigned i, unsigned j)
{
    if (dp[i].find(j) != dp[i].end())
        return;
    if (2 * i > n)
    {
        dp[i][j] = {j};
        return;
    }
    if (2 * i + 1 > n)
    {
        dp[i][j] = {min(j, y[2 * i]), max(j, y[2 * i])};
        return;
    }
    if (y[2 * i] > j && y[2 * i + 1] > j)
    {
        lexicographically_smallest(n, 2 * i, y[2 * i]);
        lexicographically_smallest(n, 2 * i + 1, y[2 * i + 1]);
        dp[i][j] = merge_subtrees(j, dp[2 * i][y[2 * i]], dp[2 * i + 1][y[2 * i + 1]]);
    }
    else if (y[2 * i] < y[2 * i + 1])
    {
        lexicographically_smallest(n, 2 * i, j);
        lexicographically_smallest(n, 2 * i + 1, y[2 * i + 1]);
        dp[i][j] = merge_subtrees(y[2 * i], dp[2 * i][j], dp[2 * i + 1][y[2 * i + 1]]);
    }
    else
    {
        lexicographically_smallest(n, 2 * i, j);
        lexicographically_smallest(n, 2 * i + 1, y[2 * i]);
        lexicographically_smallest(n, 2 * i, y[2 * i]);
        lexicographically_smallest(n, 2 * i + 1, j);

        vector<unsigned> const
            a = merge_subtrees(y[2 * i + 1], dp[2 * i][j], dp[2 * i + 1][y[2 * i]]),
            b = merge_subtrees(y[2 * i + 1], dp[2 * i][y[2 * i]], dp[2 * i + 1][j]);
        if (lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()))
            dp[i][j] = a;
        else
            dp[i][j] = b;
    }
}

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

    size_t n;
    cin >> n;
    for (size_t i = 1; i <= n; i++)
        cin >> y[i];

    lexicographically_smallest(n, 1, y[1]);
    for (unsigned x : dp[1][y[1]])
        cout << x << ' ';
    cout << '\n';
}

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