제출 #1162008

#제출 시각아이디문제언어결과실행 시간메모리
1162008_callmelucianSwap (BOI16_swap)C++17
68 / 100
274 ms257776 KiB
#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) { 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...