oj.uz

Submission #573123

# Submission time Handle Problem Language Result Execution time Memory
573123 2022-06-06T03:10:25 Z tamthegod Swap (BOI16_swap) C++14
100 / 100
 83 ms 31776 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 10;
 
int n, a[N];
map <int, int> f[N];
 
int GetPos(int u, int val) {
    if (f[u].find(val) != f[u].end()) return f[u][val];
    if (u * 2 > n) return f[u][val] = u;
    if (val < a[u * 2] && val < a[u * 2 + 1]) return f[u][val] = u;
    if (a[u * 2] < val && a[u * 2] < a[u * 2 + 1]) return f[u][val] = GetPos(u * 2, val);
    else {
        int Min = min(val, a[u * 2]);
        int Max = max(val, a[u * 2]);
        if (GetPos(u * 2, Min) < GetPos(u * 2 + 1, Min)) {
            if (val == Min) return f[u][val] = GetPos(u * 2, val);
            else return f[u][val] = GetPos(u * 2 + 1, val);
        } else {
            if (val == Min) return f[u][val] = GetPos(u * 2 + 1, val);
            else return f[u][val] = GetPos(u * 2, val);
        }
    }
//    assert(0);
}
 
int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    memset(a, 60, sizeof(a));
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int u = 1; u <= n; ++u) {
        if (u * 2 > n) continue;
        if (a[u] < a[u * 2] && a[u] < a[u * 2 + 1]) continue;
        if (a[u * 2] < a[u] && a[u * 2] < a[u * 2 + 1])
            swap(a[u * 2], a[u]);
        else {
            int Min = min(a[u], a[u * 2]);
            int Max = max(a[u], a[u * 2]);
            swap(a[u * 2 + 1], a[u]);
            if (GetPos(u * 2, Min) < GetPos(u * 2 + 1, Min)) {
                a[u * 2] = Min;
                a[u * 2 + 1] = Max;
            } else {
                a[u * 2] = Max;
                a[u * 2 + 1] = Min;
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << a[i] << ' ';
}

Compilation message

swap.cpp: In function 'int GetPos(int, int)':
swap.cpp:17:13: warning: unused variable 'Max' [-Wunused-variable]
   17 |         int Max = max(val, a[u * 2]);
      |             ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 6 ms 10492 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Correct 5 ms 10492 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 6 ms 10492 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Correct 5 ms 10492 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 5 ms 10488 KB Output is correct
10 Correct 6 ms 10496 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 6 ms 10492 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Correct 5 ms 10492 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 5 ms 10488 KB Output is correct
10 Correct 6 ms 10496 KB Output is correct
11 Correct 5 ms 10488 KB Output is correct
12 Correct 5 ms 10488 KB Output is correct
13 Correct 6 ms 10452 KB Output is correct
14 Correct 6 ms 10580 KB Output is correct
15 Correct 6 ms 10532 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 6 ms 10492 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Correct 5 ms 10492 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 5 ms 10488 KB Output is correct
10 Correct 6 ms 10496 KB Output is correct
11 Correct 5 ms 10488 KB Output is correct
12 Correct 5 ms 10488 KB Output is correct
13 Correct 6 ms 10452 KB Output is correct
14 Correct 6 ms 10580 KB Output is correct
15 Correct 6 ms 10532 KB Output is correct
16 Correct 17 ms 12756 KB Output is correct
17 Correct 17 ms 12696 KB Output is correct
18 Correct 17 ms 12756 KB Output is correct
19 Correct 21 ms 15672 KB Output is correct
20 Correct 22 ms 15644 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 6 ms 10492 KB Output is correct
3 Correct 6 ms 10488 KB Output is correct
4 Correct 5 ms 10492 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 6 ms 10452 KB Output is correct
9 Correct 5 ms 10488 KB Output is correct
10 Correct 6 ms 10496 KB Output is correct
11 Correct 5 ms 10488 KB Output is correct
12 Correct 5 ms 10488 KB Output is correct
13 Correct 6 ms 10452 KB Output is correct
14 Correct 6 ms 10580 KB Output is correct
15 Correct 6 ms 10532 KB Output is correct
16 Correct 17 ms 12756 KB Output is correct
17 Correct 17 ms 12696 KB Output is correct
18 Correct 17 ms 12756 KB Output is correct
19 Correct 21 ms 15672 KB Output is correct
20 Correct 22 ms 15644 KB Output is correct
21 Correct 55 ms 20060 KB Output is correct
22 Correct 56 ms 19928 KB Output is correct
23 Correct 53 ms 19940 KB Output is correct
24 Correct 80 ms 31700 KB Output is correct
25 Correct 83 ms 31776 KB Output is correct