# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
703024 | | 406 | Swap (BOI16_swap) | C++17 | | 1068 ms | 17012 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int L = 20;
const long long INF = 1ll << 60;
map<int, vector<int>> dp[N];
int n, a[4 * N];
void merge(vector<int> &a, const vector<int> b, const vector<int> c) {
assert(b.size() && c.size());
assert(b.size() == c.size());
int ptr = 0;
for (int i = 0; ptr < b.size(); i++) {
for (int j = 0; j < (1 << i); j++) {
a.push_back(b[j + ptr]);
}
for (int j = 0; j < (1 << i); j++) {
a.push_back(c[j + ptr]);
}
ptr += 1 << i;
}
}
void DP(int i, int j) {
if (i >= n / 2) {
dp[i][j] = {j};
return;
}
int r = a[2 * i + 1];
int l = a[2 * i];
if (j <= l && j <= r) {
DP(i * 2, l);
DP(i * 2 + 1, r);
vector<int> re{j};
merge(re, dp[i << 1][l], dp[i << 1 | 1][r]);
dp[i][j] = re;
return;
}
if (j <= l) {
DP(i * 2, j);
DP(i * 2 + 1, j);
DP(i * 2, l);
DP(i * 2 + 1, l);
vector<int> re{r};
merge(re, dp[i * 2][l], dp[i * 2 + 1][j]);
vector<int> re2{r};
merge(re2, dp[i * 2][j], dp[i * 2 + 1][l]);
dp[i][j] = min(re, re2);
return;
}
if (j <= r) {
DP(i * 2, j);
DP(i * 2 + 1, r);
vector<int> re{l};
merge(re, dp[i << 1][j], dp[i << 1 | 1][r]);
dp[i][j] = re;
return;
}
DP(i * 2, j);
DP(i * 2 + 1, j);
DP(i * 2, r);
DP(i * 2 + 1, r);
DP(i * 2, l);
DP(i * 2 + 1, l);
vector<int> re{r};
merge(re, dp[i * 2][l], dp[i * 2 + 1][j]);
vector<int> re2{r};
merge(re2, dp[i * 2][j], dp[i * 2 + 1][l]);
vector<int> re3{l};
merge(re3, dp[i * 2][j], dp[i * 2 + 1][r]);
re = min(re, re2);
re = min(re, re3);
dp[i][j] = re;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
while (n & (n - 1)) {
a[++n] = INF;
}
DP(1, a[1]);
for (auto u: dp[1][a[1]]) if (u != INF)
cout << u << ' ';
cout << '\n';
return 0;
}
Compilation message (stderr)
swap.cpp: In function 'void merge(std::vector<long long int>&, std::vector<long long int>, std::vector<long long int>)':
swap.cpp:14:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; ptr < b.size(); i++) {
| ~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |