답안 #1055355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055355	2024-08-12T18:02:07 Z	PanosPask	Swap (BOI16_swap)	C++14	100 / 100	65 ms	34132 KB

swap

/* 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

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	440 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct

Subtask #2
11.0 / 11.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #1055355

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 11.0 / 11.0

Subtask #3 27.0 / 27.0

Subtask #4 20.0 / 20.0

Subtask #5 32.0 / 32.0

Subtask #1
10.0 / 10.0

Subtask #2
11.0 / 11.0

Subtask #3
27.0 / 27.0

Subtask #4
20.0 / 20.0

Subtask #5
32.0 / 32.0