제출 #998777

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998777		underwaterkillerwhale	Swap (BOI16_swap)	C++17	0 / 100	2 ms	9820 KiB

swap

#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 ll INF = 1e17;
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 pos = 0;
    vector<int> vec = {A};
//    cout << A<<"\n";
//    iter (id, lc) cout << id <<","; cout <<"\n";
//    iter (id, rc) cout << id <<"."; cout <<"\n";

    assert (SZ(lc) >= SZ(rc));
    while (pos < SZ(rc)) {
        vec.push_back(lc[pos]);
        vec.push_back(rc[pos]);
        ++pos;
    }
    while (pos < SZ(lc)) vec.push_back(lc[pos++]);
    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) {
    if (root * 2 > n) {
        dp[root][valr] = {valr};
        return;
    }
    if (root * 2 + 1 > n) {
        dp[root][valr] = {min(valr, a[root * 2]), max(valr, a[root * 2])};
        return;
    }
    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];
//        cout << root <<" "<<A <<"hihi:\n";
        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 * 2 > n) {
//        cout << id <<"hihihi\n";
        return dp[id][val] = vector<int> (1, id);
    }
    if (id * 2 + 1 > n) {
        return dp[id][val] = {min(val, a[id * 2]), max(val, a[id * 2])};
    }
    if (dp[id].find(val) != dp[id].end())
        return dp[id][val];
//    cout << id<<" "<<val<<"hihi\n";
    Assign (id, val);
    return dp[id][val];
}

void solution () {
    cin >> n;
    rep (i, 1, n) cin >> a[i];
    vector<int> res;
    Assign (1, a[1]);
//    cout <<"\n";
    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: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32