#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 = 4e5 + 5;
vector<int> dp[mn][19][2];
int a[mn], n;
void clearData (int u) {
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(dp[nodeL][0][0], dp[nodeR][0][0]);
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(dp[nodeL][climb + 1][fp], dp[nodeR][0][0]);
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(dp[nodeL][0][0], dp[nodeR][climb + 1][fp]);
// sub-case: bring left child to right child (original root to left child)
vector<int> candT = mergeVector(dp[nodeL][climb + 1][fp], dp[nodeR][0][1]);
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];
for (int i = n + 1; i <= 2 * n + 1; i++) a[i] = 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... |