Submission #706436

#	Time	Username	Problem	Language	Result	Execution time	Memory
706436		ParsaS	Swap (BOI16_swap)	C++17	0 / 100	1 ms	468 KiB

swap

// In the name of God
//        : )
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, MOD = 1e9 + 7, inf = 1e9 + 10;
int n, a[N], b[N], par[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        par[i] = i / 2;
        b[i] = a[i];
    }
    for (int i = n + 1; i <= 2 * n + 1; i++)
        b[i] = inf;
    if (n <= 3) {
        sort(a, a + n + 1);
        for (int i = 1; i <= n; i++)
            cout << a[i] << ' ';
        return;
    }
    if (a[1] < min(a[2], a[3])) {
        par[2] = par[3] = 0;
    }
    else if (a[2] < min(a[1], a[3])) {
        a[1] = a[2];
        b[2] = b[1];
        par[2] = par[3] = 0;
    }
    else {
        b[0] = a[1];
        b[1] = b[2];
        b[2] = b[3] = inf;
        a[1] = a[3];
    }
    for (int i = 2; i <= n; i++) {
        int lc = b[2 * i], rc = b[2 * i + 1];
        int ul = 2 * i, ur = 2 * i + 1;
        int v = i, mn = b[0];
        while (v) {
            mn = min(mn, b[v]);
            v = par[v];
        }
        if (mn < min(lc, rc)) {
            a[i] = mn;
            v = i;
            while (b[v] != mn)
                v = par[v];
            b[v] = inf;
            par[ul] = par[ur] = 0;
        }
        else if (lc < min(mn, rc)) {
            a[i] = lc;
            b[lc] = inf;
            par[rc] = 0;
        }
        else {
            a[i] = rc;
            b[i] = lc;
            b[ur] = inf;
            b[ul] = inf;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int tc = 1; //cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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