oj.uz

Submission #1055355

# Submission time Handle Problem Language Result Execution time Memory
1055355 2024-08-12T18:02:07 Z PanosPask Swap (BOI16_swap) C++14
100 / 100
 65 ms 34132 KB 
/* For an explanation of the solution, read this:
 * https://codeforces.com/blog/entry/44769?#comment-293999
 */

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> a;
vector<int> res;

int counter = 0;
vector<int> tin;
vector<int> tout;

/* dp[i][j]:
 * If the value at node i is j, at what position will it end up if we
 * perform the swaps optimally
 */
vector<unordered_map<int, int>> dp;

int process(int node, int v)
{
    if (dp[node].count(v)) {
        return dp[node][v];
    }

    int l = 2 * node + 1, r = 2 * node + 2;

    if (l >= N) {
        return node;
    }
    if (r >= N) {
        if (v < a[l]) {
            return node;
        }
        else {
            return process(l, v);
        }
    }

    if (v < min(a[l], a[r])) {
        // Do not make any swaps
        dp[node][v] = node;
    }
    else if (a[l] < min(v, a[r])) {
        // Only make the first swap to bring a[l] at the root
        dp[node][v] = process(l, v);
    }
    else {
        // a[r] is placed at the root

        int mn = min(a[l], v);

        int place_left = process(l, mn);
        int place_right = process(r, mn);

        if (place_left < place_right) {
            // Placing the minimum element left results in a better outcome
            if (mn == v) {
                dp[node][v] = process(l, v);
            }
            else {
                dp[node][v] = process(r, v);
            }
        }
        else {
            // Placing the minimum element right results in a better outcome
            if (mn == v) {
                dp[node][v] = process(r, v);
            }
            else {
                dp[node][v] = process(l, v);
            }
        }
    }

    return dp[node][v];
}

bool ancestor(int a, int b)
{
    return tin[a] <= tin[b] && tout[a] >= tout[b];
}

void dfs(int node)
{
    if (node >= N) {
        return;
    }

    tin[node] = counter++;

    dfs(2 * node + 1);
    dfs(2 * node + 2);

    tout[node] = counter;
}

void make_result(int node, int v)
{
    int l = 2 * node + 1;
    int r = 2 * node + 2;

    if (process(node, v) == node) {
        res[node] = v;

        if (l < N) {
            make_result(l, a[l]);
        }
        if (r < N) {
            make_result(r, a[r]);
        }
    }
    else if (ancestor(l, process(node, v))) {
        make_result(l, v);

        res[node] = a[l];
        if (r < N) {
            res[node] = min(a[l], a[r]);
            make_result(r, max(a[l], a[r]));
        }
    }
    else {
        make_result(r, v);
        res[node] = a[r];
        make_result(l, a[l]);
    }
}

int main(void)
{
    scanf("%d", &N);

    a.resize(N);
    tin.resize(N);
    tout.resize(N);
    res.resize(N);
    dp.resize(N);

    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    
    process(0, a[0]);
    dfs(0);
    make_result(0, a[0]);

    for (int i = 0; i < N; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");

    return 0;
}

Compilation message

swap.cpp: In function 'int main()':
swap.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
swap.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 14 ms 8280 KB Output is correct
17 Correct 14 ms 8284 KB Output is correct
18 Correct 16 ms 8284 KB Output is correct
19 Correct 14 ms 8628 KB Output is correct
20 Correct 16 ms 8796 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 440 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 14 ms 8280 KB Output is correct
17 Correct 14 ms 8284 KB Output is correct
18 Correct 16 ms 8284 KB Output is correct
19 Correct 14 ms 8628 KB Output is correct
20 Correct 16 ms 8796 KB Output is correct
21 Correct 56 ms 32596 KB Output is correct
22 Correct 59 ms 32592 KB Output is correct
23 Correct 65 ms 32596 KB Output is correct
24 Correct 57 ms 34128 KB Output is correct
25 Correct 57 ms 34132 KB Output is correct