| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 576108 |
2022-06-12T10:59:07 Z |
Do_you_copy |
Swap (BOI16_swap) |
C++14 |
|
87 ms |
37176 KB |
#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();
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
