#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;
}
Compilation message
/tmp/ccmukT6R.o: In function `main':
swap.cpp:(.text.startup+0x21): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x28): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x2f): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x39): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x50): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x8e): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x128): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
swap.cpp:(.text.startup+0x158): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/tmp/ccmukT6R.o: In function `_GLOBAL__sub_I_dp':
swap.cpp:(.text.startup+0x1b7): relocation truncated to fit: R_X86_64_PC32 against `.bss'
swap.cpp:(.text.startup+0x1d1): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1a): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
