Submission #1292979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292979		jwpassion1	Swap (BOI16_swap)	C++20	21 / 100	1 ms	576 KiB

swap

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int n;
int a[200001], dp[524288];

void dfs(int node, int val) {
    //cout << "dfs " << node << '\n';
    int l = node << 1, r = node << 1 | 1;
    //cout << l << ' ' << r << '\n';
    if (n < l) dp[node] = node;
    else if (n < r) {
        if (val < a[l]) dp[node] = node;
        else dp[node] = l;
    }
    else {
        if (a[l] >= a[r]) {
            if (val < a[r]) dp[node] = node;
            else if (val < a[l]) {
                dfs(l, val);
                dfs(r, val);
                dp[node] = min(dp[l], dp[r]);
            }
            else {
                dfs(l, a[l]);
                dfs(r, a[l]);
                if (a[l] < a[r]) {
                    dfs(r, val);
                    dp[node] = dp[r];
                }
                else if (a[l] > a[r]) {
                    dfs(l, val);
                    dp[node] = dp[l];
                }
                else assert(false);
            }
        }
        else {
            if (val < a[l]) dp[node] = node;
            else {
                dfs(l, val);
                dp[node] = dp[l];
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        int l = i << 1, r = i << 1 | 1;
        if (r <= n) {
            if (a[r] <= a[i] && a[r] <= a[l]) {
                dfs(l, min(a[i], a[l]));
                dfs(r, min(a[i], a[l]));
                //cout << i << " : " << l << " = " << dp[l] << ", " << r << " = " << dp[r] << endl;
                swap(a[i], a[r]);
                int mi = min(a[l], a[r]), ma = max(a[l], a[r]);
                if (dp[l] < dp[r]) {
                    a[l] = mi;
                    a[r] = ma;
                }
                else if (dp[l] > dp[r]) {
                    a[l] = ma;
                    a[r] = mi;
                }
                else assert(false);
            }
            else if (a[l] < a[i]) swap(a[i], a[l]);
        }
        else if (l == n) {
            if (a[l] < a[i]) swap(a[i], a[l]);
        }
        cout << a[i] << ' ';
        //for (int j = 1; j <= n; j++) cout << a[j] << ' ';
        //cout << '\n';
    }
    cout << '\n';
}

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