oj.uz

Submission #702665

# Submission time Handle Problem Language Result Execution time Memory
702665 2023-02-24T18:00:05 Z finn__ Swap (BOI16_swap) C++17
68 / 100
 704 ms 262144 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(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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9724 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9724 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 10108 KB Output is correct
13 Correct 6 ms 9976 KB Output is correct
14 Correct 8 ms 10708 KB Output is correct
15 Correct 8 ms 10636 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9724 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 10108 KB Output is correct
13 Correct 6 ms 9976 KB Output is correct
14 Correct 8 ms 10708 KB Output is correct
15 Correct 8 ms 10636 KB Output is correct
16 Correct 74 ms 28180 KB Output is correct
17 Correct 81 ms 27840 KB Output is correct
18 Correct 89 ms 28372 KB Output is correct
19 Correct 400 ms 105760 KB Output is correct
20 Correct 413 ms 104916 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9724 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 6 ms 9724 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 10108 KB Output is correct
13 Correct 6 ms 9976 KB Output is correct
14 Correct 8 ms 10708 KB Output is correct
15 Correct 8 ms 10636 KB Output is correct
16 Correct 74 ms 28180 KB Output is correct
17 Correct 81 ms 27840 KB Output is correct
18 Correct 89 ms 28372 KB Output is correct
19 Correct 400 ms 105760 KB Output is correct
20 Correct 413 ms 104916 KB Output is correct
21 Correct 303 ms 87720 KB Output is correct
22 Correct 289 ms 88948 KB Output is correct
23 Correct 291 ms 89176 KB Output is correct
24 Runtime error 704 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -