Submission #998825

#	Time	Username	Problem	Language	Result	Execution time	Memory
998825		underwaterkillerwhale	Swap (BOI16_swap)	C++17	68 / 100	627 ms	262144 KiB

swap

#pragma GCC optimize("conserve-stack")

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;

int n;
int a[N];
map<int, vector<int>> dp[N];

vector<int> Merge (int A, vector<int> lc, vector<int> rc) {
    int ptr1 = 0, ptr2 = 0;
    static vector<int> vec;
    vec = {A};
    rep (i, 0, 20) {
        if ((1 << i) > SZ(lc) - ptr1) break;
        rep (j, 1, (1 << i)) vec.push_back(lc[ptr1++]);
        rep (j, 1, (1 << i)) {
            if (ptr2 < SZ(rc)) vec.push_back(rc[ptr2++]);
        }
    }
    while (ptr1 < SZ(lc)) vec.push_back(lc[ptr1++]);
    return vec;
}

bool compare (vector<int> &v1, vector<int> &v2) {
    int pos = 0;
    assert (SZ(v1) == SZ(v2));
    while (v1[pos] == v2[pos]) ++pos;
    return v1[pos] < v2[pos];
}

vector<int> calc (int id, int val);
void Assign (int root, int valr) {
    int lc = root * 2, rc = root * 2 + 1;
    if (valr < a[lc] && valr < a[rc]) {
        vector<int> t1 = calc (lc, a[lc]), t2 = calc (rc, a[rc]);
        dp[root][valr] = Merge (valr, t1, t2);
    }
    else if (a[lc] < min (valr, a[rc])) {
        vector<int> t1 = calc (lc, valr), t2 = calc (rc, a[rc]);
        dp[root][valr] = Merge (a[lc], t1, t2);
    }
    else {
        int B = min (valr, a[lc]);
        int C = max (valr, a[lc]);
        int A = a[rc];
        vector<int> t1 = Merge (A, calc (lc, B), calc (rc, C)), t2 = Merge (A, calc (lc, C), calc (rc, B));
        if (compare (t1, t2)) dp[root][valr] = t1;
        else dp[root][valr] = t2;
    }
}

vector<int> calc (int id, int val) {
    if (id > n) return vector<int> (0);
    if (id * 2 > n) {
        return vector<int> (1, val);
    }
    if (id * 2 + 1 > n) {
        return {min(val, a[id * 2]), max(val, a[id * 2])};
    }
    if (dp[id].find(val) != dp[id].end())
        return dp[id][val];
    Assign (id, val);
    return dp[id][val];
}

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
//    n = 1e5;
//    rep (i ,1, n) a[i] = i;
//    random_shuffle(a + 1, a + 1 + n);
    vector<int> res;
    Assign (1, a[1]);
    iter (&id, dp[1][a[1]]) cout << id <<" ";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
5 10
1 2
3 1
4 2
5 3
1 4
2 3
3 5
4 5
3 4
1 4

*/

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