oj.uz

Submission #245598

# Submission time Handle Problem Language Result Execution time Memory
245598 2020-07-07T00:06:49 Z thecodingwizard Swap (BOI16_swap) C++11
68 / 100
 671 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200000;

int n, A[maxn+10];
vector<int> memo[maxn+10][36];
int pa[maxn+10][36];

vector<int> merge(int root, vector<int> &L, vector<int> &R) {
    vector<int> res;
    res.push_back(root);
    int lidx = 0, ridx = 0;
    int cur = 1;
    while (lidx < L.size() || ridx < R.size()) {
        for (int i = 0; i < cur; i++) {
            if (lidx < L.size()) res.push_back(L[lidx++]);
        }
        for (int i = 0; i < cur; i++) {
            if (ridx < R.size()) res.push_back(R[ridx++]);
        }
        cur *= 2;
    }
    return res;
}

vector<int> &dp(int u, int par) {
    if (memo[u][par].size() > 0) return memo[u][par];
    int cur = pa[u][par];
    int l = u*2, r = u*2+1;
    if (l > n && r > n) {
        memo[u][par].push_back(cur);
        return memo[u][par];
    } else if (r > n) {
        if (A[l] < cur) {
            memo[u][par].push_back(A[l]);
            memo[u][par].push_back(cur);
        } else {
            memo[u][par].push_back(cur);
            memo[u][par].push_back(A[l]);
        }
        return memo[u][par];
    }

    int L = A[l], R = A[r];
    // no swap
    if (cur < L && cur < R) {
        return memo[u][par] = merge(cur, dp(l, 0), dp(r, 0));
    }

    // swap left
    if (cur > L && L < R) {
        return memo[u][par] = merge(L, dp(l, par+2), dp(r, 0));
    }

    // swap right
    // swap both
    if (R < cur && R < L) {
        vector<int> swapRight = merge(R, dp(l, 0), dp(r, par+2));
        vector<int> swapBoth = merge(R, dp(l, par+2), dp(r, 3));
        return memo[u][par] = min(swapRight, swapBoth);
    }
}

int main() {
    cin >> n; for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) {
        int x = i;
        int ctr = 0;
        while (x) {
            pa[i][ctr*2] = A[x];
            if (x*2 <= n) pa[i][ctr*2+1] = A[x*2];
            x /= 2;
            ctr++;
        }
    }
    vector<int> ans = dp(1, 0);
    for (int v : ans) cout << v << " ";
    cout << endl;
    return 0;
}

Compilation message

swap.cpp: In function 'std::vector<int> merge(int, std::vector<int>&, std::vector<int>&)':
swap.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lidx < L.size() || ridx < R.size()) {
            ~~~~~^~~~~~~~~~
swap.cpp:16:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lidx < L.size() || ridx < R.size()) {
                               ~~~~~^~~~~~~~~~
swap.cpp:18:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (lidx < L.size()) res.push_back(L[lidx++]);
                 ~~~~~^~~~~~~~~~
swap.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ridx < R.size()) res.push_back(R[ridx++]);
                 ~~~~~^~~~~~~~~~
swap.cpp: In function 'std::vector<int>& dp(int, int)':
swap.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 169464 KB Output is correct
2 Correct 99 ms 169464 KB Output is correct
3 Correct 111 ms 169464 KB Output is correct
4 Correct 111 ms 169464 KB Output is correct
5 Correct 101 ms 169464 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 169464 KB Output is correct
2 Correct 99 ms 169464 KB Output is correct
3 Correct 111 ms 169464 KB Output is correct
4 Correct 111 ms 169464 KB Output is correct
5 Correct 101 ms 169464 KB Output is correct
6 Correct 99 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 100 ms 169464 KB Output is correct
9 Correct 116 ms 169464 KB Output is correct
10 Correct 117 ms 169464 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 169464 KB Output is correct
2 Correct 99 ms 169464 KB Output is correct
3 Correct 111 ms 169464 KB Output is correct
4 Correct 111 ms 169464 KB Output is correct
5 Correct 101 ms 169464 KB Output is correct
6 Correct 99 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 100 ms 169464 KB Output is correct
9 Correct 116 ms 169464 KB Output is correct
10 Correct 117 ms 169464 KB Output is correct
11 Correct 114 ms 169720 KB Output is correct
12 Correct 110 ms 169712 KB Output is correct
13 Correct 107 ms 169720 KB Output is correct
14 Correct 106 ms 169976 KB Output is correct
15 Correct 118 ms 169976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 169464 KB Output is correct
2 Correct 99 ms 169464 KB Output is correct
3 Correct 111 ms 169464 KB Output is correct
4 Correct 111 ms 169464 KB Output is correct
5 Correct 101 ms 169464 KB Output is correct
6 Correct 99 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 100 ms 169464 KB Output is correct
9 Correct 116 ms 169464 KB Output is correct
10 Correct 117 ms 169464 KB Output is correct
11 Correct 114 ms 169720 KB Output is correct
12 Correct 110 ms 169712 KB Output is correct
13 Correct 107 ms 169720 KB Output is correct
14 Correct 106 ms 169976 KB Output is correct
15 Correct 118 ms 169976 KB Output is correct
16 Correct 178 ms 185768 KB Output is correct
17 Correct 175 ms 185464 KB Output is correct
18 Correct 180 ms 185968 KB Output is correct
19 Correct 458 ms 217256 KB Output is correct
20 Correct 462 ms 216872 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 169464 KB Output is correct
2 Correct 99 ms 169464 KB Output is correct
3 Correct 111 ms 169464 KB Output is correct
4 Correct 111 ms 169464 KB Output is correct
5 Correct 101 ms 169464 KB Output is correct
6 Correct 99 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 100 ms 169464 KB Output is correct
9 Correct 116 ms 169464 KB Output is correct
10 Correct 117 ms 169464 KB Output is correct
11 Correct 114 ms 169720 KB Output is correct
12 Correct 110 ms 169712 KB Output is correct
13 Correct 107 ms 169720 KB Output is correct
14 Correct 106 ms 169976 KB Output is correct
15 Correct 118 ms 169976 KB Output is correct
16 Correct 178 ms 185768 KB Output is correct
17 Correct 175 ms 185464 KB Output is correct
18 Correct 180 ms 185968 KB Output is correct
19 Correct 458 ms 217256 KB Output is correct
20 Correct 462 ms 216872 KB Output is correct
21 Correct 458 ms 239164 KB Output is correct
22 Correct 432 ms 239908 KB Output is correct
23 Correct 438 ms 240096 KB Output is correct
24 Runtime error 671 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -