| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 672497 |
2022-12-16T10:39:34 Z |
tamthegod |
Swap (BOI16_swap) |
C++14 |
|
84 ms |
31720 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]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 7 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 9 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 7 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 9 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10452 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10484 KB |
Output is correct |
| 12 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10480 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10580 KB |
Output is correct |
| 15 |
Correct |
5 ms |
10580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 7 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 9 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10452 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10484 KB |
Output is correct |
| 12 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10480 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10580 KB |
Output is correct |
| 15 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 16 |
Correct |
19 ms |
12692 KB |
Output is correct |
| 17 |
Correct |
17 ms |
12704 KB |
Output is correct |
| 18 |
Correct |
17 ms |
12780 KB |
Output is correct |
| 19 |
Correct |
22 ms |
15644 KB |
Output is correct |
| 20 |
Correct |
24 ms |
15704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 2 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 3 |
Correct |
6 ms |
10428 KB |
Output is correct |
| 4 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 5 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10452 KB |
Output is correct |
| 7 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 8 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 9 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10452 KB |
Output is correct |
| 11 |
Correct |
6 ms |
10484 KB |
Output is correct |
| 12 |
Correct |
5 ms |
10452 KB |
Output is correct |
| 13 |
Correct |
6 ms |
10480 KB |
Output is correct |
| 14 |
Correct |
6 ms |
10580 KB |
Output is correct |
| 15 |
Correct |
5 ms |
10580 KB |
Output is correct |
| 16 |
Correct |
19 ms |
12692 KB |
Output is correct |
| 17 |
Correct |
17 ms |
12704 KB |
Output is correct |
| 18 |
Correct |
17 ms |
12780 KB |
Output is correct |
| 19 |
Correct |
22 ms |
15644 KB |
Output is correct |
| 20 |
Correct |
24 ms |
15704 KB |
Output is correct |
| 21 |
Correct |
57 ms |
20044 KB |
Output is correct |
| 22 |
Correct |
54 ms |
19968 KB |
Output is correct |
| 23 |
Correct |
65 ms |
19940 KB |
Output is correct |
| 24 |
Correct |
83 ms |
31720 KB |
Output is correct |
| 25 |
Correct |
84 ms |
31620 KB |
Output is correct |
