#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
vector<int> mergeVector (const vector<int> &a, const vector<int> &b) {
vector<int> ans;
int pos = 0;
for (int sz = 1; pos < max(a.size(), b.size()); pos += sz, sz <<= 1) {
for (int j = pos; j < pos + sz && j < a.size(); j++) ans.push_back(a[j]);
for (int j = pos; j < pos + sz && j < b.size(); j++) ans.push_back(b[j]);
}
return ans;
}
const int mn = 2e5 + 5;
vector<int> dp[mn][19][2], emp;
int a[2 * mn], n;
void clearData (int u) {
if (u > n) return;
for (int climb = 0; (u >> climb) > 0; climb++)
for (int fp = 0; fp <= (u & 1); fp++) dp[u][climb][fp].clear();
}
void dfs (int u) {
if (u > n) return;
int nodeL = u << 1, nodeR = u << 1 | 1;
dfs(nodeL), dfs(nodeR);
for (int climb = 0; (u >> climb) > 0; climb++) {
for (int fp = 0; fp <= ((u >> climb & 1) && (u >> climb) > 1); fp++) {
int rootVal = a[(u >> climb) ^ fp];
/// case 1: leave everything as it is
if (rootVal < min(a[nodeL], a[nodeR])) {
dp[u][climb][fp] = mergeVector((nodeL <= n ? dp[nodeL][0][0] : emp), (nodeR <= n ? dp[nodeR][0][0] : emp));
dp[u][climb][fp].insert(dp[u][climb][fp].begin(), rootVal);
}
/// case 2: bring the left child up
else if (a[nodeL] < a[nodeR]) {
dp[u][climb][fp] = mergeVector((nodeL <= n ? dp[nodeL][climb + 1][fp] : emp), (nodeR <= n ? dp[nodeR][0][0] : emp));
dp[u][climb][fp].insert(dp[u][climb][fp].begin(), a[nodeL]);
}
/// case 3: bring the right child up
else if (a[nodeL] > a[nodeR]) {
// sub-case: do not bring left child to right child
vector<int> candO = mergeVector((nodeL <= n ? dp[nodeL][0][0] : emp), (nodeR <= n ? dp[nodeR][climb + 1][fp] : emp));
// sub-case: bring left child to right child (original root to left child)
vector<int> candT = mergeVector((nodeL <= n ? dp[nodeL][climb + 1][fp] : emp), (nodeR <= n ? dp[nodeR][0][1] : emp));
dp[u][climb][fp] = min(candO, candT);
dp[u][climb][fp].insert(dp[u][climb][fp].begin(), a[nodeR]);
}
/// edge-case
else dp[u][climb][fp].push_back(rootVal);
}
}
clearData(nodeL), clearData(nodeR);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
fill(a + n + 1, a + 2 * n + 2, INT_MAX);
dfs(1);
for (int u : dp[1][0][0]) cout << u << " ";
return 0;
}
# | 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... |