oj.uz

답안 #245629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245629 2020-07-07T01:48:38 Z thecodingwizard Swap (BOI16_swap) C++11
68 / 100
 1000 ms 256760 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;
            int cur = A[idx];
 
            v[i<<1][0] = v[i<<1^1][0] = true;
 
            if (A[i<<1]<A[idx]&&A[i<<1]<A[i<<1^1]) {
                v[i<<1][j+2] = true;
            } else if (A[i<<1^1]<cur&&A[i<<1^1]<A[i<<1]) {
                v[i<<1^1][3] = v[i<<1][j+2] = v[i<<1^1][j+2] = 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 (l <= n) {
            for (int j = 0; j < 36; j++) if (v[l][j]) vector<int>().swap(dp[l][j]);
        }
        if (r <= n) {
            for (int j = 0; j < 36; j++) if (v[r][j]) vector<int>().swap(dp[r][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

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 169464 KB Output is correct
2 Correct 106 ms 169464 KB Output is correct
3 Correct 116 ms 169484 KB Output is correct
4 Correct 106 ms 169464 KB Output is correct
5 Correct 104 ms 169464 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 169464 KB Output is correct
2 Correct 106 ms 169464 KB Output is correct
3 Correct 116 ms 169484 KB Output is correct
4 Correct 106 ms 169464 KB Output is correct
5 Correct 104 ms 169464 KB Output is correct
6 Correct 111 ms 169464 KB Output is correct
7 Correct 105 ms 169464 KB Output is correct
8 Correct 105 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 108 ms 169464 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 169464 KB Output is correct
2 Correct 106 ms 169464 KB Output is correct
3 Correct 116 ms 169484 KB Output is correct
4 Correct 106 ms 169464 KB Output is correct
5 Correct 104 ms 169464 KB Output is correct
6 Correct 111 ms 169464 KB Output is correct
7 Correct 105 ms 169464 KB Output is correct
8 Correct 105 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 108 ms 169464 KB Output is correct
11 Correct 122 ms 169592 KB Output is correct
12 Correct 107 ms 169592 KB Output is correct
13 Correct 105 ms 169488 KB Output is correct
14 Correct 115 ms 169688 KB Output is correct
15 Correct 126 ms 169848 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 169464 KB Output is correct
2 Correct 106 ms 169464 KB Output is correct
3 Correct 116 ms 169484 KB Output is correct
4 Correct 106 ms 169464 KB Output is correct
5 Correct 104 ms 169464 KB Output is correct
6 Correct 111 ms 169464 KB Output is correct
7 Correct 105 ms 169464 KB Output is correct
8 Correct 105 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 108 ms 169464 KB Output is correct
11 Correct 122 ms 169592 KB Output is correct
12 Correct 107 ms 169592 KB Output is correct
13 Correct 105 ms 169488 KB Output is correct
14 Correct 115 ms 169688 KB Output is correct
15 Correct 126 ms 169848 KB Output is correct
16 Correct 160 ms 174072 KB Output is correct
17 Correct 163 ms 174072 KB Output is correct
18 Correct 172 ms 174072 KB Output is correct
19 Correct 286 ms 189048 KB Output is correct
20 Correct 305 ms 188792 KB Output is correct

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 169464 KB Output is correct
2 Correct 106 ms 169464 KB Output is correct
3 Correct 116 ms 169484 KB Output is correct
4 Correct 106 ms 169464 KB Output is correct
5 Correct 104 ms 169464 KB Output is correct
6 Correct 111 ms 169464 KB Output is correct
7 Correct 105 ms 169464 KB Output is correct
8 Correct 105 ms 169464 KB Output is correct
9 Correct 104 ms 169464 KB Output is correct
10 Correct 108 ms 169464 KB Output is correct
11 Correct 122 ms 169592 KB Output is correct
12 Correct 107 ms 169592 KB Output is correct
13 Correct 105 ms 169488 KB Output is correct
14 Correct 115 ms 169688 KB Output is correct
15 Correct 126 ms 169848 KB Output is correct
16 Correct 160 ms 174072 KB Output is correct
17 Correct 163 ms 174072 KB Output is correct
18 Correct 172 ms 174072 KB Output is correct
19 Correct 286 ms 189048 KB Output is correct
20 Correct 305 ms 188792 KB Output is correct
21 Correct 377 ms 187984 KB Output is correct
22 Correct 419 ms 187896 KB Output is correct
23 Correct 365 ms 188600 KB Output is correct
24 Execution timed out 1022 ms 256760 KB Time limit exceeded
25 Halted 0 ms 0 KB -