oj.uz

Submission #245632

# Submission time Handle Problem Language Result Execution time Memory
245632 2020-07-07T01:53:12 Z thecodingwizard Swap (BOI16_swap) C++11
100 / 100
 965 ms 232060 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
 
using namespace std;
 
const int maxn = 200000;
 
int n, A[maxn+10];
vector<int> dp[maxn+10][36], tmp1, tmp2;
bool v[maxn+10][40];
 
void merge(vector<int> &res, vector<int> &L, vector<int> &R) {
    for (int len = 1, i = 0, j = 0; i < L.size() || j < R.size(); i += len, j += len, len *= 2) {
        for (int k = 0; k < len && i+k<L.size(); k++) res.push_back(L[i+k]);
        for (int k = 0; k < len && i+k<R.size(); k++) res.push_back(R[i+k]);
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n; for (int i = 1; i <= n; i++) cin >> A[i];
    for (int i = 1; i <= n; i++) for (int j = 0; j < 36; j++) v[i][j] = false;
    v[1][0] = 1;
    for (int i = 1; 2*i+1 <= n; i++) {
        for (int j = 0; j < 36; j++) {
            if (!v[i][j]) continue;
            int idx = i>>(j/2);
            if (j&1) idx *= 2;
 
            // if left is smallest
            if (A[i<<1]<A[idx]&&A[i<<1]<A[i<<1^1]) {
                v[i<<1^1][0] = v[i<<1][j+2] = true;
            } else if (A[i<<1^1]<A[idx]&&A[i<<1^1]<A[i<<1]) {
                v[i<<1][0] = v[i<<1^1][3] = v[i<<1][j+2] = v[i<<1^1][j+2] = true;
            } else {
                v[i<<1][0] = v[i<<1^1][0] = true;
            }
        }
    }
    for (int i = n; i; i--) {
        int l = i<<1, r = i<<1^1;
        for (int j = 0; j < 36; j++) {
            if (!v[i][j]) continue;
            int idx = i>>(j/2);
            if (j&1) idx *= 2;
            int cur = A[idx];
 
            if (l > n && r > n) {
                dp[i][j] = {cur};
            } else if (r > n) {
                dp[i][j] = {min(A[l],cur),max(A[l],cur)};
            } else {
                int L = A[l], R = A[r];
                if (R < cur && R < L) {
                    tmp1 = {R}, tmp2 = {R};
                    // swap right
                    merge(tmp1, dp[l][0], dp[r][j+2]);
                    // swap both
                    merge(tmp2, dp[l][j+2], dp[r][3]);
                    dp[i][j] = min(tmp1, tmp2);
                } else {
                    dp[i][j]={cur<L?cur:L};
                    // no swap / swap left
                    merge(dp[i][j], dp[l][cur<L?0:j+2], dp[r][0]);
                }
            }
        }
 
        if ((i<<1^1)<=n) {
            for (int k = 0; k < 2; k++)
            for (int j = 0; j < 36; j++) if (v[i<<1|k][j]) vector<int>().swap(dp[i<<1|k][j]);
        }
    }
    for (int v : dp[1][0]) cout << v << " ";
    return 0;
}

Compilation message

swap.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:13:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int len = 1, i = 0, j = 0; i < L.size() || j < R.size(); i += len, j += len, len *= 2) {
                                     ~~^~~~~~~~~~
swap.cpp:13:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int len = 1, i = 0, j = 0; i < L.size() || j < R.size(); i += len, j += len, len *= 2) {
                                                     ~~^~~~~~~~~~
swap.cpp:14:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k = 0; k < len && i+k<L.size(); k++) res.push_back(L[i+k]);
                                    ~~~^~~~~~~~~
swap.cpp:15:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int k = 0; k < len && i+k<R.size(); k++) res.push_back(R[i+k]);
                                    ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 169464 KB Output is correct
2 Correct 121 ms 169484 KB Output is correct
3 Correct 112 ms 169464 KB Output is correct
4 Correct 115 ms 169464 KB Output is correct
5 Correct 107 ms 169408 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 169464 KB Output is correct
2 Correct 121 ms 169484 KB Output is correct
3 Correct 112 ms 169464 KB Output is correct
4 Correct 115 ms 169464 KB Output is correct
5 Correct 107 ms 169408 KB Output is correct
6 Correct 154 ms 169464 KB Output is correct
7 Correct 114 ms 169464 KB Output is correct
8 Correct 121 ms 169464 KB Output is correct
9 Correct 108 ms 169464 KB Output is correct
10 Correct 110 ms 169464 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 169464 KB Output is correct
2 Correct 121 ms 169484 KB Output is correct
3 Correct 112 ms 169464 KB Output is correct
4 Correct 115 ms 169464 KB Output is correct
5 Correct 107 ms 169408 KB Output is correct
6 Correct 154 ms 169464 KB Output is correct
7 Correct 114 ms 169464 KB Output is correct
8 Correct 121 ms 169464 KB Output is correct
9 Correct 108 ms 169464 KB Output is correct
10 Correct 110 ms 169464 KB Output is correct
11 Correct 125 ms 169532 KB Output is correct
12 Correct 116 ms 169604 KB Output is correct
13 Correct 125 ms 169592 KB Output is correct
14 Correct 114 ms 169720 KB Output is correct
15 Correct 108 ms 169720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 169464 KB Output is correct
2 Correct 121 ms 169484 KB Output is correct
3 Correct 112 ms 169464 KB Output is correct
4 Correct 115 ms 169464 KB Output is correct
5 Correct 107 ms 169408 KB Output is correct
6 Correct 154 ms 169464 KB Output is correct
7 Correct 114 ms 169464 KB Output is correct
8 Correct 121 ms 169464 KB Output is correct
9 Correct 108 ms 169464 KB Output is correct
10 Correct 110 ms 169464 KB Output is correct
11 Correct 125 ms 169532 KB Output is correct
12 Correct 116 ms 169604 KB Output is correct
13 Correct 125 ms 169592 KB Output is correct
14 Correct 114 ms 169720 KB Output is correct
15 Correct 108 ms 169720 KB Output is correct
16 Correct 163 ms 173560 KB Output is correct
17 Correct 157 ms 173560 KB Output is correct
18 Correct 179 ms 173624 KB Output is correct
19 Correct 285 ms 183544 KB Output is correct
20 Correct 259 ms 183416 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 169464 KB Output is correct
2 Correct 121 ms 169484 KB Output is correct
3 Correct 112 ms 169464 KB Output is correct
4 Correct 115 ms 169464 KB Output is correct
5 Correct 107 ms 169408 KB Output is correct
6 Correct 154 ms 169464 KB Output is correct
7 Correct 114 ms 169464 KB Output is correct
8 Correct 121 ms 169464 KB Output is correct
9 Correct 108 ms 169464 KB Output is correct
10 Correct 110 ms 169464 KB Output is correct
11 Correct 125 ms 169532 KB Output is correct
12 Correct 116 ms 169604 KB Output is correct
13 Correct 125 ms 169592 KB Output is correct
14 Correct 114 ms 169720 KB Output is correct
15 Correct 108 ms 169720 KB Output is correct
16 Correct 163 ms 173560 KB Output is correct
17 Correct 157 ms 173560 KB Output is correct
18 Correct 179 ms 173624 KB Output is correct
19 Correct 285 ms 183544 KB Output is correct
20 Correct 259 ms 183416 KB Output is correct
21 Correct 333 ms 185852 KB Output is correct
22 Correct 329 ms 185592 KB Output is correct
23 Correct 374 ms 185616 KB Output is correct
24 Correct 885 ms 231928 KB Output is correct
25 Correct 965 ms 232060 KB Output is correct