oj.uz

Submission #714986

# Submission time Handle Problem Language Result Execution time Memory
714986 2023-03-25T16:10:37 Z Stickfish Swap (BOI16_swap) C++17
21 / 100
 2 ms 792 KB 
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100;
vector<int> dp[MAXN][MAXN];
vector<int> subtr[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;
}

signed main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i * 2 + 1 >= n) {
            for (int t = 0; t < n; ++t) dp[i][t] = {t};
            continue;
        }
        if (i * 2 + 2 >= n) {
            for (int t = 0; t < n; ++t) {
                dp[i][t] = {min(t, p[i * 2 + 1]), max(t, p[i * 2 + 1])};
            }
            continue;
        }
        for (int t = 0; t < n; ++t) {
            int lchd = i * 2 + 1;
            int rchd = i * 2 + 2;
            if (t < p[lchd] && t < p[rchd]) {
                dp[i][t] = unite_subtr(dp[lchd][p[lchd]], dp[rchd][p[rchd]]);
                dp[i][t][0] = t;
                continue;
            }
            if (p[lchd] < t && p[lchd] < p[rchd]) {
                dp[i][t] = unite_subtr(dp[lchd][t], dp[rchd][p[rchd]]);
                dp[i][t][0] = p[lchd];
                continue;
            }
            // p[rchd] < t, p[lchd]
            vector<int> dp0 = unite_subtr(dp[lchd][p[lchd]], dp[rchd][t]);
            vector<int> dp1 = unite_subtr(dp[lchd][t], dp[rchd][p[lchd]]);
            dp[i][t] = min(dp0, dp1);
            dp[i][t][0] = p[rchd];
        }
    }
    for (auto x : dp[0][p[0]]) {
        cout << x + 1 << ' ';
    }
    cout << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Runtime error 2 ms 792 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Runtime error 2 ms 792 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Runtime error 2 ms 792 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -