답안 #576108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
576108	2022-06-12T10:59:07 Z	Do_you_copy	Swap (BOI16_swap)	C++14	100 / 100	87 ms	37176 KB

swap

#include <bits/stdc++.h>
#define ll long long
#define taskname ""
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

const ll Mod = 1000000007;
const int maxN = 2e5 + 1;
int n;
int a[8 * maxN + 1];

map <int, int> m[maxN];

int get(int id, int val) {
    if (m[id].find(val) != m[id].end())
        return m[id][val];

    if (val < a[id * 2] && val < a[id * 2 + 1])
        return m[id][val] = id;

    if (a[id * 2] < val && a[id * 2] < a[id * 2 + 1])
        return m[id][val] = get(id * 2, val);

    int Min = min(val, a[id * 2]);

    if (get(id * 2, Min) < get(id * 2 + 1, Min)) {
        if (val == Min)
            return m[id][val] = get(id * 2, val);

        return m[id][val] = get(id * 2 + 1, val);
    }

    if (val == Min)
        return m[id][val] = get(id * 2 + 1, val);

    return m[id][val] = get(id * 2, val);
}

void Init() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = n + 1; i <= 8 * maxN; ++i)
        a[i] = INT_MAX;

    for (int i = 1; i <= n; ++i) {
        if (a[i] < a[i * 2] && a[i] < a[i * 2 + 1])
            continue;

        if (a[i * 2] < a[i] && a[i * 2] < a[i * 2 + 1])
            swap(a[i * 2], a[i]);
        else {
            int Min = min(a[i], a[i * 2]);
            int Max = max(a[i], a[i * 2]);
            swap(a[i * 2 + 1], a[i]);

            if (get(i * 2, Min) < get(i * 2 + 1, Min)) {
                a[i * 2] = Min;
                a[i * 2 + 1] = Max;
            } else {
                a[i * 2] = Max;
                a[i * 2 + 1] = Min;
            }
        }
    }

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

int main() {
    faster
    Init();
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	8 ms	15956 KB	Output is correct
3	Correct	8 ms	15956 KB	Output is correct
4	Correct	8 ms	15868 KB	Output is correct
5	Correct	8 ms	15872 KB	Output is correct

Subtask #2

11.0 / 11.0

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

Subtask #3

27.0 / 27.0

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

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	8 ms	15956 KB	Output is correct
3	Correct	8 ms	15956 KB	Output is correct
4	Correct	8 ms	15868 KB	Output is correct
5	Correct	8 ms	15872 KB	Output is correct
6	Correct	8 ms	15956 KB	Output is correct
7	Correct	9 ms	15956 KB	Output is correct
8	Correct	9 ms	15956 KB	Output is correct
9	Correct	9 ms	15956 KB	Output is correct
10	Correct	8 ms	15956 KB	Output is correct
11	Correct	8 ms	15956 KB	Output is correct
12	Correct	8 ms	15964 KB	Output is correct
13	Correct	8 ms	15956 KB	Output is correct
14	Correct	8 ms	15956 KB	Output is correct
15	Correct	8 ms	15956 KB	Output is correct
16	Correct	19 ms	18184 KB	Output is correct
17	Correct	19 ms	18176 KB	Output is correct
18	Correct	19 ms	18236 KB	Output is correct
19	Correct	29 ms	21068 KB	Output is correct
20	Correct	27 ms	21204 KB	Output is correct

Subtask #5

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	15956 KB	Output is correct
2	Correct	8 ms	15956 KB	Output is correct
3	Correct	8 ms	15956 KB	Output is correct
4	Correct	8 ms	15868 KB	Output is correct
5	Correct	8 ms	15872 KB	Output is correct
6	Correct	8 ms	15956 KB	Output is correct
7	Correct	9 ms	15956 KB	Output is correct
8	Correct	9 ms	15956 KB	Output is correct
9	Correct	9 ms	15956 KB	Output is correct
10	Correct	8 ms	15956 KB	Output is correct
11	Correct	8 ms	15956 KB	Output is correct
12	Correct	8 ms	15964 KB	Output is correct
13	Correct	8 ms	15956 KB	Output is correct
14	Correct	8 ms	15956 KB	Output is correct
15	Correct	8 ms	15956 KB	Output is correct
16	Correct	19 ms	18184 KB	Output is correct
17	Correct	19 ms	18176 KB	Output is correct
18	Correct	19 ms	18236 KB	Output is correct
19	Correct	29 ms	21068 KB	Output is correct
20	Correct	27 ms	21204 KB	Output is correct
21	Correct	61 ms	25560 KB	Output is correct
22	Correct	59 ms	25508 KB	Output is correct
23	Correct	58 ms	25548 KB	Output is correct
24	Correct	86 ms	37132 KB	Output is correct
25	Correct	87 ms	37176 KB	Output is correct