oj.uz

Submission #245600

# Submission time Handle Problem Language Result Execution time Memory
245600 2020-07-07T00:18:27 Z thecodingwizard Swap (BOI16_swap) C++11
68 / 100
 575 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];

void merge(vector<int> &res, int root, vector<int> &L, vector<int> &R) {
    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;
    }
}

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) {
        merge(memo[u][par], cur, dp(l, 0), dp(r, 0));
        return memo[u][par];
    }

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

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

        return memo[u][par];
    }

    assert(false);
}

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 'void merge(std::vector<int>&, int, std::vector<int>&, std::vector<int>&)':
swap.cpp:15:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lidx < L.size() || ridx < R.size()) {
            ~~~~~^~~~~~~~~~
swap.cpp:15:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lidx < L.size() || ridx < R.size()) {
                               ~~~~~^~~~~~~~~~
swap.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (lidx < L.size()) res.push_back(L[lidx++]);
                 ~~~~~^~~~~~~~~~
swap.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (ridx < R.size()) res.push_back(R[ridx++]);
                 ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 169464 KB Output is correct
2 Correct 104 ms 169464 KB Output is correct
3 Correct 109 ms 169464 KB Output is correct
4 Correct 98 ms 169464 KB Output is correct
5 Correct 98 ms 169464 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 169464 KB Output is correct
2 Correct 104 ms 169464 KB Output is correct
3 Correct 109 ms 169464 KB Output is correct
4 Correct 98 ms 169464 KB Output is correct
5 Correct 98 ms 169464 KB Output is correct
6 Correct 98 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 98 ms 169464 KB Output is correct
9 Correct 97 ms 169464 KB Output is correct
10 Correct 106 ms 169468 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 169464 KB Output is correct
2 Correct 104 ms 169464 KB Output is correct
3 Correct 109 ms 169464 KB Output is correct
4 Correct 98 ms 169464 KB Output is correct
5 Correct 98 ms 169464 KB Output is correct
6 Correct 98 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 98 ms 169464 KB Output is correct
9 Correct 97 ms 169464 KB Output is correct
10 Correct 106 ms 169468 KB Output is correct
11 Correct 113 ms 169720 KB Output is correct
12 Correct 113 ms 169720 KB Output is correct
13 Correct 109 ms 169720 KB Output is correct
14 Correct 101 ms 169868 KB Output is correct
15 Correct 100 ms 169976 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 169464 KB Output is correct
2 Correct 104 ms 169464 KB Output is correct
3 Correct 109 ms 169464 KB Output is correct
4 Correct 98 ms 169464 KB Output is correct
5 Correct 98 ms 169464 KB Output is correct
6 Correct 98 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 98 ms 169464 KB Output is correct
9 Correct 97 ms 169464 KB Output is correct
10 Correct 106 ms 169468 KB Output is correct
11 Correct 113 ms 169720 KB Output is correct
12 Correct 113 ms 169720 KB Output is correct
13 Correct 109 ms 169720 KB Output is correct
14 Correct 101 ms 169868 KB Output is correct
15 Correct 100 ms 169976 KB Output is correct
16 Correct 187 ms 185516 KB Output is correct
17 Correct 177 ms 185204 KB Output is correct
18 Correct 172 ms 185652 KB Output is correct
19 Correct 424 ms 216528 KB Output is correct
20 Correct 456 ms 216176 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 169464 KB Output is correct
2 Correct 104 ms 169464 KB Output is correct
3 Correct 109 ms 169464 KB Output is correct
4 Correct 98 ms 169464 KB Output is correct
5 Correct 98 ms 169464 KB Output is correct
6 Correct 98 ms 169464 KB Output is correct
7 Correct 99 ms 169464 KB Output is correct
8 Correct 98 ms 169464 KB Output is correct
9 Correct 97 ms 169464 KB Output is correct
10 Correct 106 ms 169468 KB Output is correct
11 Correct 113 ms 169720 KB Output is correct
12 Correct 113 ms 169720 KB Output is correct
13 Correct 109 ms 169720 KB Output is correct
14 Correct 101 ms 169868 KB Output is correct
15 Correct 100 ms 169976 KB Output is correct
16 Correct 187 ms 185516 KB Output is correct
17 Correct 177 ms 185204 KB Output is correct
18 Correct 172 ms 185652 KB Output is correct
19 Correct 424 ms 216528 KB Output is correct
20 Correct 456 ms 216176 KB Output is correct
21 Correct 464 ms 237692 KB Output is correct
22 Correct 454 ms 238488 KB Output is correct
23 Correct 428 ms 238728 KB Output is correct
24 Runtime error 575 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -