답안 #933202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933202	2024-02-25T09:02:24 Z	LucaIlie	Swap (BOI16_swap)	C++17	100 / 100	172 ms	49752 KB

swap

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
int v[2 * MAX_N + 2];
unordered_map<int, int> dp[MAX_N + 1];

int DP( int i, int x ) {
    if ( dp[i][x] != 0 )
        return dp[i][x];

    if ( x < v[2 * i] && x < v[2 * i + 1] )
        dp[i][x] = i;
    else if ( v[2 * i] < v[2 * i + 1] )
        dp[i][x] = DP( 2 * i, x );
    else {
        if ( x < v[2 * i] )  {
            DP( 2 *  i, x );
            DP( 2 * i + 1, x );
            if ( dp[2 * i][x] < dp[2 * i + 1][x] )
                dp[i][x] = DP( 2 * i, x );
            else
                dp[i][x] = DP( 2 * i + 1, x );
        }
        else {
            DP( 2 * i, v[2 * i] );
            DP( 2 * i + 1, v[2 * i] );
            if ( dp[2 * i][v[2 * i]] < dp[2 * i + 1][v[2 * i]] )
                dp[i][x] = DP( 2 * i + 1, x );
            else
                dp[i][x] = DP( 2 * i, x );
        }
    }

    return dp[i][x];
}

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i];
    for ( int i = n + 1; i <= 2 * n + 1; i++ )
        v[i] = n + 1;

    for ( int i = 1; 2 * i + 1 <= n; i++ ) {
        if (  v[2 * i] < v[i] && v[2 * i] < v[2 * i + 1] )
            swap( v[i], v[2 * i] );
        else if ( v[2 * i + 1] < v[i] && v[2 * i + 1] < v[2 * i] ) {
            swap( v[i], v[2 * i + 1] );

            if ( v[2 * i] < v[2 * i + 1] ) {
                if ( DP( 2 * i, v[2 * i] ) > DP( 2 * i + 1, v[2 * i] ) )
                    swap( v[2 * i], v[2 * i + 1] );
            } else {
                if ( DP( 2 * i, v[2 * i + 1] ) < DP( 2 * i + 1, v[2 * i + 1] ) )
                    swap( v[2 * i], v[2 * i + 1] );
            }
        }
    }
    if ( v[n / 2] > v[n] )
        swap( v[n / 2], v[n] );

    for ( int i = 1; i <= n; i++ )
        cout << v[i] << " ";

    return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	3 ms	12904 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	3 ms	12904 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	4 ms	12888 KB	Output is correct
12	Correct	3 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Correct	3 ms	12892 KB	Output is correct
15	Correct	3 ms	12892 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	3 ms	12904 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	4 ms	12888 KB	Output is correct
12	Correct	3 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Correct	3 ms	12892 KB	Output is correct
15	Correct	3 ms	12892 KB	Output is correct
16	Correct	27 ms	16984 KB	Output is correct
17	Correct	25 ms	16980 KB	Output is correct
18	Correct	26 ms	17016 KB	Output is correct
19	Correct	37 ms	21588 KB	Output is correct
20	Correct	38 ms	21596 KB	Output is correct

Subtask #5

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	3 ms	12892 KB	Output is correct
4	Correct	3 ms	12892 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12892 KB	Output is correct
7	Correct	3 ms	12904 KB	Output is correct
8	Correct	3 ms	12892 KB	Output is correct
9	Correct	3 ms	12892 KB	Output is correct
10	Correct	3 ms	12892 KB	Output is correct
11	Correct	4 ms	12888 KB	Output is correct
12	Correct	3 ms	12892 KB	Output is correct
13	Correct	4 ms	12892 KB	Output is correct
14	Correct	3 ms	12892 KB	Output is correct
15	Correct	3 ms	12892 KB	Output is correct
16	Correct	27 ms	16984 KB	Output is correct
17	Correct	25 ms	16980 KB	Output is correct
18	Correct	26 ms	17016 KB	Output is correct
19	Correct	37 ms	21588 KB	Output is correct
20	Correct	38 ms	21596 KB	Output is correct
21	Correct	102 ms	30676 KB	Output is correct
22	Correct	107 ms	31444 KB	Output is correct
23	Correct	102 ms	31332 KB	Output is correct
24	Correct	172 ms	49752 KB	Output is correct
25	Correct	169 ms	49744 KB	Output is correct