Submission #1162008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162008		_callmelucian	Swap (BOI16_swap)	C++17	68 / 100	274 ms	257776 KiB

swap

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 0 / 32