oj.uz

Submission #714995

# Submission time Handle Problem Language Result Execution time Memory
714995 2023-03-25T16:56:54 Z Stickfish Swap (BOI16_swap) C++17
100 / 100
 422 ms 140164 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

const int MAXN = 202020;
vector<vector<int>> dp[MAXN];
vector<int> subtr[MAXN];
int p[MAXN];

vector<int> unite_subtr(vector<int> ltr, vector<int> rtr) {
    auto lit = ltr.begin();
    auto rit = rtr.begin();
    vector<int> ans = {-1};
    for (int sz = 1; lit < ltr.end() || rit < rtr.end(); sz *= 2) {
        for (int i = 0; i < sz && lit + i < ltr.end(); ++i)
            ans.push_back(lit[i]);
        for (int i = 0; i < sz && rit + i < rtr.end(); ++i)
            ans.push_back(rit[i]);
        lit += sz;
        rit += sz;
    }
    return ans;
}

vector<int> merge(vector<int> a, vector<int> b) {
    auto bit = b.begin();
    vector<int> ans;
    for (auto ait = a.begin(); ait < a.end(); ++ait) {
        while (bit < b.end() && *bit < *ait) {
            ans.push_back(*(bit++));
        }
        ans.push_back(*ait);
    }
    while (bit < b.end()) {
        ans.push_back(*(bit++));
    }
    return ans;
}

vector<int> get_substit(vector<int> v, int pvl, int nvl) {
    vector<int> ans;
    for (auto x : v) {
        if (x == pvl)
            ans.push_back(nvl);
        else
            ans.push_back(x);
    }
    return ans;
}

vector<int> get_dp(int i, int t) {
    int lchd = i * 2 + 1;
    int rchd = i * 2 + 2;
    if (subtr[i].size() == 1)
        return {t};
    if (subtr[i].size() == 2)
        return {min(t, p[lchd]), max(t, p[lchd])};

    int ti = lower_bound(subtr[i].begin(), subtr[i].end(), t) - subtr[i].begin();
    assert(t < subtr[i][ti]);
    if (t != subtr[i][ti] - 1) {
        return get_substit(get_dp(i, subtr[i][ti] - 1), subtr[i][ti] - 1, t);
    }
    if (dp[i][ti].size()) {
        return dp[i][ti];
    }

    if (t < p[lchd] && t < p[rchd]) {
        dp[i][ti] = unite_subtr(get_dp(lchd, p[lchd]), get_dp(rchd, p[rchd]));
        dp[i][ti][0] = t;
        return dp[i][ti];
    }
    if (p[lchd] < t && p[lchd] < p[rchd]) {
        dp[i][ti] = unite_subtr(get_dp(lchd, t), get_dp(rchd, p[rchd]));
        dp[i][ti][0] = p[lchd];
        return dp[i][ti];
    }
    vector<int> dp0 = unite_subtr(get_dp(lchd, p[lchd]), get_dp(rchd, t));
    vector<int> dp1 = unite_subtr(get_dp(lchd, t), get_dp(rchd, p[lchd]));
    dp[i][ti] = min(dp0, dp1);
    dp[i][ti][0] = p[rchd];
    return dp[i][ti];
}

signed main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    for (int i = n - 1; i > 0; --i) {
        int rt = (i - 1) / 2;
        subtr[rt] = merge(subtr[rt], subtr[i]);
        subtr[rt] = merge(subtr[rt], {p[i]});
    }
    for (int i = 0; i < n; ++i) {
        subtr[i].push_back(n + 1);
        dp[i].resize(subtr[i].size());
    }
    for (auto x : get_dp(0, p[0])) {
        cout << x + 1 << ' ';
    }
    cout << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 10196 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 8 ms 10068 KB Output is correct
15 Correct 7 ms 10068 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 10196 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 8 ms 10068 KB Output is correct
15 Correct 7 ms 10068 KB Output is correct
16 Correct 93 ms 38140 KB Output is correct
17 Correct 98 ms 38228 KB Output is correct
18 Correct 89 ms 38400 KB Output is correct
19 Correct 73 ms 36260 KB Output is correct
20 Correct 73 ms 36284 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 6 ms 9692 KB Output is correct
6 Correct 6 ms 9684 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 10068 KB Output is correct
12 Correct 6 ms 10196 KB Output is correct
13 Correct 6 ms 10068 KB Output is correct
14 Correct 8 ms 10068 KB Output is correct
15 Correct 7 ms 10068 KB Output is correct
16 Correct 93 ms 38140 KB Output is correct
17 Correct 98 ms 38228 KB Output is correct
18 Correct 89 ms 38400 KB Output is correct
19 Correct 73 ms 36260 KB Output is correct
20 Correct 73 ms 36284 KB Output is correct
21 Correct 399 ms 139256 KB Output is correct
22 Correct 373 ms 139200 KB Output is correct
23 Correct 422 ms 140164 KB Output is correct
24 Correct 306 ms 128356 KB Output is correct
25 Correct 315 ms 128396 KB Output is correct