| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 375284 | Mamnoon_Siam | Swap (BOI16_swap) | C++17 | 0 ms | 0 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;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
const int N = 4e5 + 3;
vi dp[N][N];
int a[N], n, nn;
vi merge(vi p, vi q) {
vi r;
int pw = 1;
int i = 0, j = 0;
while(i < sz(p) or j < sz(q)) {
r.insert(r.end(), p.begin()+i, p.begin()+min(sz(p), i+pw));
r.insert(r.end(), q.begin()+j, q.begin()+min(sz(q), j+pw));
i = min(i+pw, sz(p));
j = min(j+pw, sz(q));
pw *= 2;
}
return r;
}
vi f(int u, int k) {
if(sz(dp[u][k])) return dp[u][k];
vi& ret = dp[u][k];
if(2*u > nn) return ret = {k};
{ // don't use any edge
vi l = f(2*u, a[2*u]);
vi r = f(2*u+1, a[2*u+1]);
ret = merge(l, r);
ret.insert(ret.begin(), k);
}
{ // use only left edge
vi l = f(2*u, k);
vi r = f(2*u+1, a[2*u+1]);
vi tmp = merge(l, r);
tmp.insert(tmp.begin(), a[2*u]);
ret = min(ret, tmp);
}
{ // use only right edge
vi l = f(2*u, a[2*u]);
vi r = f(2*u+1, k);
vi tmp = merge(l, r);
tmp.insert(tmp.begin(), a[2*u+1]);
ret = min(ret, tmp);
}
{ // use both edges
vi l = f(2*u, k);
vi r = f(2*u+1, a[2*u]);
vi tmp = merge(l, r);
tmp.insert(tmp.begin(), a[2*u+1]);
ret = min(ret, tmp);
}
return ret;
}
int main(int argc, char* argv[]) {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
cin >> n;
nn = 1;
while(nn-1 < n) nn *= 2;
nn--;
for(int i = 1; i <= n; ++i)
cin >> a[i];
for(int i = n+1; i <= nn; ++i)
a[i] = n+1;
vi ans = f(1, a[1]);
for(int i = 0; i < n; ++i)
cout << ans[i] << ' ';
cout << endl;
}