oj.uz

Submission #702662

# Submission time Handle Problem Language Result Execution time Memory
702662 2023-02-24T17:54:23 Z finn__ Swap (BOI16_swap) C++17
0 / 100
 6 ms 9720 KB 
#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(y[i], 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, y[i]);
        lexicographically_smallest(n, 2 * i + 1, y[2 * i + 1]);
        dp[i][j] = merge_subtrees(y[2 * i], dp[2 * i][y[i]], dp[2 * i + 1][y[2 * i + 1]]);
    }
    else
    {
        lexicographically_smallest(n, 2 * i, y[i]);
        lexicographically_smallest(n, 2 * i + 1, y[2 * i]);

        lexicographically_smallest(n, 2 * i, y[2 * i]);
        lexicographically_smallest(n, 2 * i + 1, y[i]);
        vector<unsigned> const
            a = merge_subtrees(y[2 * i + 1], dp[2 * i][y[i]], dp[2 * i + 1][y[2 * i]]),
            b = merge_subtrees(y[2 * i + 1], dp[2 * i][y[2 * i]], dp[2 * i + 1][y[i]]);
        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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -