#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N];
unordered_map<int, int> mp[N];
int ind(int v, int x) {
if (mp[v].find(x) != mp[v].end()) return mp[v][x];
if (v * 2 > n) return mp[v][x] = v;
if (x < a[v * 2] && x < a[v * 2 + 1]) return mp[v][x] = v;
if (a[v * 2] < x && a[v * 2] < a[v * 2 + 1]) return mp[v][x] = ind(v * 2, x);
else {
int mn = min(x, a[v * 2]), mx = max(x, a[v * 2]);
if (ind(v * 2, mn) < ind(v * 2 + 1, mn))
if (x == mn) return mp[v][x] = ind(v * 2, x);
else return mp[v][x] = ind(v * 2 + 1, x);
else
if (x == mn) return mp[v][x] = ind(v * 2 + 1, x);
else return mp[v][x] = ind(v * 2, x);
}
}
int main() {
ios:: sync_with_stdio(0), cin.tie(0);
cin >> n;
memset(a, 63, sizeof a);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if (i * 2 > n) continue;
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 mn = min(a[i], a[i * 2]), mx = max(a[i], a[i * 2]);
swap(a[i * 2 + 1], a[i]);
if (ind(i * 2, mn) < ind(i * 2 + 1, mn)) a[i * 2] = mn, a[i * 2 + 1] = mx;
else a[i * 2] = mx, a[i * 2 + 1] = mn;
}
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
cout << '\n';
}
Compilation message
swap.cpp: In function 'int ind(int, int)':
swap.cpp:15:36: warning: unused variable 'mx' [-Wunused-variable]
15 | int mn = min(x, a[v * 2]), mx = max(x, a[v * 2]);
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12128 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12128 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12148 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12128 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12148 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
4 ms |
12124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12128 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12148 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 16 |
Correct |
18 ms |
16572 KB |
Output is correct |
| 17 |
Correct |
18 ms |
16728 KB |
Output is correct |
| 18 |
Correct |
18 ms |
16728 KB |
Output is correct |
| 19 |
Correct |
29 ms |
21488 KB |
Output is correct |
| 20 |
Correct |
28 ms |
21072 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12192 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12128 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12148 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 9 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 11 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 13 |
Correct |
5 ms |
12124 KB |
Output is correct |
| 14 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 15 |
Correct |
4 ms |
12124 KB |
Output is correct |
| 16 |
Correct |
18 ms |
16572 KB |
Output is correct |
| 17 |
Correct |
18 ms |
16728 KB |
Output is correct |
| 18 |
Correct |
18 ms |
16728 KB |
Output is correct |
| 19 |
Correct |
29 ms |
21488 KB |
Output is correct |
| 20 |
Correct |
28 ms |
21072 KB |
Output is correct |
| 21 |
Correct |
69 ms |
30804 KB |
Output is correct |
| 22 |
Correct |
67 ms |
30800 KB |
Output is correct |
| 23 |
Correct |
74 ms |
30544 KB |
Output is correct |
| 24 |
Correct |
122 ms |
48980 KB |
Output is correct |
| 25 |
Correct |
125 ms |
49220 KB |
Output is correct |
