Submission #702670

#	Time	Username	Problem	Language	Result	Execution time	Memory
702670		finn__	Swap (BOI16_swap)	C++17	68 / 100	520 ms	262144 KiB

swap

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

#define N 200001

map<unsigned, unsigned *> dp[N];
map<unsigned, size_t> sz[N];
unsigned y[N];

unsigned *merge_subtrees(
    unsigned f, size_t x, size_t y, unsigned const *const a, unsigned const *const b)
{
    unsigned *c = (unsigned *)malloc((x + y + 1) * sizeof *c);
    c[0] = f;
    size_t k = 0, h = 1;
    for (size_t i = 1; k < x; i <<= 1)
    {
        for (size_t j = k; j < x && j < k + i; j++)
            c[h++] = a[j];
        for (size_t j = k; j < y && j < k + i; j++)
            c[h++] = 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] = (unsigned *)malloc(sizeof(unsigned));
        dp[i][j][0] = j;
        sz[i][j] = 1;
        return;
    }
    if (2 * i + 1 > n)
    {
        dp[i][j] = (unsigned *)malloc(2 * sizeof(unsigned));
        dp[i][j][0] = min(j, y[2 * i]), dp[i][j][1] = max(j, y[2 * i]);
        sz[i][j] = 2;
        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, sz[2 * i][y[2 * i]], sz[2 * i + 1][y[2 * i + 1]], dp[2 * i][y[2 * i]], dp[2 * i + 1][y[2 * i + 1]]);
        sz[i][j] = sz[2 * i][y[2 * i]] + sz[2 * i + 1][y[2 * i + 1]] + 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], sz[2 * i][j], sz[2 * i + 1][y[2 * i + 1]], dp[2 * i][j], dp[2 * i + 1][y[2 * i + 1]]);
        sz[i][j] = sz[2 * i][j] + sz[2 * i + 1][y[2 * i + 1]] + 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);

        sz[i][j] = sz[2 * i][j] + sz[2 * i + 1][y[2 * i]] + 1;
        unsigned
            *a = merge_subtrees(y[2 * i + 1], sz[2 * i][j], sz[2 * i + 1][y[2 * i]], dp[2 * i][j], dp[2 * i + 1][y[2 * i]]),
            *b = merge_subtrees(y[2 * i + 1], sz[2 * i][y[2 * i]], sz[2 * i + 1][j], dp[2 * i][y[2 * i]], dp[2 * i + 1][j]);
        if (lexicographical_compare(a, a + sz[i][j], b, b + sz[i][j]))
            dp[i][j] = a, free(b);
        else
            dp[i][j] = b, free(a);
    }
}

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 (size_t i = 0; i < sz[1][y[1]]; i++)
        cout << dp[1][y[1]][i] << ' ';
    cout << '\n';
}

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