| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1048861 |
2024-08-08T10:00:22 Z |
TAhmed33 |
Swap (BOI16_swap) |
C++ |
|
306 ms |
69860 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
vector <int> merge (int x, vector <int> a, vector <int> b) {
vector <int> ret = {x};
reverse(a.begin(), a.end()); reverse(b.begin(), b.end());
for (int i = 0; ; i++) {
if (a.empty() || b.empty()) break;
for (int k = 0; k < (1 << i); k++) {
ret.push_back(a.back()); a.pop_back();
}
for (int k = 0; k < (1 << i); k++) {
ret.push_back(b.back()); b.pop_back();
}
}
return ret;
}
int nn, n, a[MAXN];
vector <pair <int, vector <int>>> dp[MAXN];
vector <pair <int, int>> bad[MAXN];
void insert (int i, int j, vector <int> x) {
dp[i].push_back({j, x});
}
vector <int> get (int i, int j) {
pair <int, vector <int>> z = {j, {0}};
auto x = lower_bound(dp[i].begin(), dp[i].end(), z);
return (*x).second;
}
void insert2 (int i, int j) {
pair <int, int> g = {j, 0};
auto h = lower_bound(bad[i].begin(), bad[i].end(), g) - bad[i].begin();
bad[i][h].second = 1;
}
int get2 (int i, int j) {
pair <int, int> g = {j, 0};
auto h = lower_bound(bad[i].begin(), bad[i].end(), g);
return (*h).second;
}
void solve () {
cin >> n; nn = n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (__builtin_popcount(n + 1) != 1) {
a[++n] = n;
}
bad[1].push_back({a[1], 0});
for (int i = 1; i <= n; i++) {
vector <int> x;
int j = i;
while (j >= 1) {
x.push_back(a[j]);
if (2 * j <= n) x.push_back(a[2 * j]);
if (2 * j + 1 <= n) x.push_back(a[2 * j + 1]);
j /= 2;
}
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
for (auto j : x) {
bad[i].push_back({j, 0});
}
}
insert2(1, a[1]);
for (int i = 1; i <= n; i++) {
for (auto [j, k] : bad[i]) {
if (!k) {
continue;
}
if (2 * i > n) {
continue;
}
if (j < a[2 * i] && j < a[2 * i + 1]) {
insert2(2 * i, a[2 * i]);
insert2(2 * i + 1, a[2 * i + 1]);
continue;
}
if (a[2 * i] < j && a[2 * i] < a[2 * i + 1]) {
insert2(2 * i, j); insert2(2 * i + 1, a[2 * i + 1]);
continue;
}
insert2(2 * i, a[2 * i]); insert2(2 * i + 1, j);
insert2(2 * i, j); insert2(2 * i + 1, a[2 * i]);
}
}
for (int i = n; i >= 1; i--) {
vector <int> x;
int j = i;
while (j >= 1) {
x.push_back(a[j]);
if (2 * j <= n) x.push_back(a[2 * j]);
if (2 * j + 1 <= n) x.push_back(a[2 * j + 1]);
j /= 2;
}
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
for (auto j : x) {
if (!get2(i, j)) {
continue;
}
if (2 * i > n) {
insert(i, j, {j});
continue;
}
if (j < a[2 * i] && j < a[2 * i + 1]) {
insert(i, j, merge(j, get(2 * i, a[2 * i]), get(2 * i + 1, a[2 * i + 1])));
continue;
}
if (a[2 * i] < j && a[2 * i] < a[2 * i + 1]) {
insert(i, j, merge(a[2 * i], get(2 * i, j), get(2 * i + 1, a[2 * i + 1])));
continue;
}
insert(i, j, min({
merge(a[2 * i + 1], get(2 * i, a[2 * i]), get(2 * i + 1, j)),
merge(a[2 * i + 1], get(2 * i, j), get(2 * i + 1, a[2 * i]))
}));
}
if (2 * i <= n) dp[2 * i].clear();
if (2 * i + 1 <= n) dp[2 * i + 1].clear();
}
auto g = get(1, a[1]);
for (int j = 0; j < nn; j++) {
cout << g[j] << " ";
}
cout << '\n';
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
Compilation message
swap.cpp: In function 'void solve()':
swap.cpp:45:5: warning: operation on 'n' may be undefined [-Wsequence-point]
45 | a[++n] = n;
| ^~~
swap.cpp:45:5: warning: operation on 'n' may be undefined [-Wsequence-point]
swap.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for (auto [j, k] : bad[i]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 12 |
Correct |
4 ms |
10332 KB |
Output is correct |
| 13 |
Correct |
3 ms |
10212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
10616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 12 |
Correct |
4 ms |
10332 KB |
Output is correct |
| 13 |
Correct |
3 ms |
10212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
10616 KB |
Output is correct |
| 16 |
Correct |
192 ms |
37108 KB |
Output is correct |
| 17 |
Correct |
189 ms |
36944 KB |
Output is correct |
| 18 |
Correct |
208 ms |
37152 KB |
Output is correct |
| 19 |
Correct |
294 ms |
69860 KB |
Output is correct |
| 20 |
Correct |
306 ms |
69688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 7 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 9 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 12 |
Correct |
4 ms |
10332 KB |
Output is correct |
| 13 |
Correct |
3 ms |
10212 KB |
Output is correct |
| 14 |
Correct |
4 ms |
10588 KB |
Output is correct |
| 15 |
Correct |
4 ms |
10616 KB |
Output is correct |
| 16 |
Correct |
192 ms |
37108 KB |
Output is correct |
| 17 |
Correct |
189 ms |
36944 KB |
Output is correct |
| 18 |
Correct |
208 ms |
37152 KB |
Output is correct |
| 19 |
Correct |
294 ms |
69860 KB |
Output is correct |
| 20 |
Correct |
306 ms |
69688 KB |
Output is correct |
| 21 |
Runtime error |
16 ms |
21080 KB |
Execution killed with signal 11 |
| 22 |
Halted |
0 ms |
0 KB |
- |
