Submission #706448

#	Time	Username	Problem	Language	Result	Execution time	Memory
706448		ParsaS	Swap (BOI16_swap)	C++17	0 / 100	25 ms	38524 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], par[N];
set<int> st[N];

void ins(int v, int x) {
    st[v].insert(x);
}
void ers(int v, int x) {
    st[v].erase(st[v].find(x));
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        par[i] = i / 2;
        st[i].insert(a[i]);
        st[i].insert(inf);
    }
    for (int i = n + 1; i <= 2 * n + 1; i++) {
        st[i].insert(inf);
        st[i].insert(inf - 1);
        a[i] = inf - 1;
    }
    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])) {
        ers(2, a[2]), ins(2, a[1]);
        a[1] = a[2];
        par[2] = par[3] = 0;
    }
    else {
        ins(1, a[2]);
        ers(2, a[2]);
        ers(3, a[3]);
        a[1] = a[3];
    }
    for (int i = 2; i <= n; i++) {
        int lc = a[2 * i], rc = a[2 * i + 1];
        int ul = 2 * i, ur = 2 * i + 1;
        int v = i, mn = inf;
        while (v) {
            mn = min(mn, *st[v].begin());
            v = par[v];
        }
        if (mn < min(lc, rc)) {
            v = i;
            while (!st[v].count(mn))
                v = par[v];
            ers(v, mn);
            a[i] = mn;
            par[ul] = par[ur] = 0;
        }
        else if (lc < min(mn, rc)) {
            ers(ul, lc);
            a[i] = lc;
            par[rc] = 0;
        }
        else {
            ers(ul, a[ul]);
            ers(ur, a[ur]);
            ins(i, lc);
            a[i] = rc;
        }
    }
    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