oj.uz

답안 #322228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
322228 2020-11-14T09:52:34 Z dolphingarlic Swap (BOI16_swap) C++14
68 / 100
 480 ms 262148 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int a[1 << 18];
vector<int> dp[1 << 18][18][2], tmp1, tmp2;

void merge(vector<int> &ret, vector<int> &l, vector<int> &r) {
    for (int i = 0, j = 1; i < l.size(); i += j, j <<= 1) {
        for (int k = i; k < i + j; k++) ret.push_back(l[k]);
        for (int k = i; k < i + j; k++) ret.push_back(r[k]);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    int orig = n;
    while (__builtin_popcount(n + 1) != 1) a[++n] = n;

    for (int node = n; node; node--) {
        for (int i = 0; node >> i; i++) for (int j : {0, 1}) {
            if (!(((node >> i + 1) << 1) + j)) continue;
            int val = a[((node >> i + 1) << 1) + j];

            if (node * 2 > n) dp[node][i][j] = {val};
            else {
                int mn = min({val, a[2 * node], a[2 * node + 1]});
                if (mn == val) {
                    dp[node][i][j] = {val};
                    merge(dp[node][i][j], dp[2 * node][0][0], dp[2 * node + 1][0][1]);
                } else if (mn == a[2 * node]) {
                    dp[node][i][j] = {a[2 * node]};
                    merge(dp[node][i][j], dp[2 * node][i + 1][j], dp[2 * node + 1][0][1]);
                } else {
                    tmp1 = tmp2 = {a[2 * node + 1]};
                    merge(tmp1, dp[2 * node][0][0], dp[2 * node + 1][i + 1][j]);
                    merge(tmp2, dp[2 * node][i + 1][j], dp[2 * node + 1][0][0]);
                    dp[node][i][j] = min(tmp1, tmp2);
                }
            }
        }

        if (node * 2 <= n) {
            for (int i = 0; node * 2 >> i; i++) for (int j : {0, 1}) {
                vector<int>().swap(dp[node * 2][i][j]);
                vector<int>().swap(dp[node * 2 + 1][i][j]);
            }
        }
    }

    for (int i = 0; i < orig; i++) printf("%d ", dp[1][0][1][i]);
    return 0;
}

Compilation message

swap.cpp: In function 'void merge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
swap.cpp:9:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = 0, j = 1; i < l.size(); i += j, j <<= 1) {
      |                            ~~^~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:20:46: warning: operation on 'n' may be undefined [-Wsequence-point]
   20 |     while (__builtin_popcount(n + 1) != 1) a[++n] = n;
      |                                              ^~~
swap.cpp:20:46: warning: operation on 'n' may be undefined [-Wsequence-point]
swap.cpp:24:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |             if (!(((node >> i + 1) << 1) + j)) continue;
      |                             ~~^~~
swap.cpp:25:37: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |             int val = a[((node >> i + 1) << 1) + j];
      |                                   ~~^~~
swap.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
swap.cpp:18:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     for (int i = 1; i <= n; i++) scanf("%d", a + i);
      |                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 222008 KB Output is correct
2 Correct 132 ms 221932 KB Output is correct
3 Correct 134 ms 221932 KB Output is correct
4 Correct 131 ms 221932 KB Output is correct
5 Correct 136 ms 222060 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 222008 KB Output is correct
2 Correct 132 ms 221932 KB Output is correct
3 Correct 134 ms 221932 KB Output is correct
4 Correct 131 ms 221932 KB Output is correct
5 Correct 136 ms 222060 KB Output is correct
6 Correct 133 ms 222060 KB Output is correct
7 Correct 133 ms 222060 KB Output is correct
8 Correct 135 ms 222060 KB Output is correct
9 Correct 132 ms 221932 KB Output is correct
10 Correct 134 ms 221932 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 222008 KB Output is correct
2 Correct 132 ms 221932 KB Output is correct
3 Correct 134 ms 221932 KB Output is correct
4 Correct 131 ms 221932 KB Output is correct
5 Correct 136 ms 222060 KB Output is correct
6 Correct 133 ms 222060 KB Output is correct
7 Correct 133 ms 222060 KB Output is correct
8 Correct 135 ms 222060 KB Output is correct
9 Correct 132 ms 221932 KB Output is correct
10 Correct 134 ms 221932 KB Output is correct
11 Correct 133 ms 222264 KB Output is correct
12 Correct 135 ms 222132 KB Output is correct
13 Correct 134 ms 222316 KB Output is correct
14 Correct 134 ms 222316 KB Output is correct
15 Correct 136 ms 222316 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 222008 KB Output is correct
2 Correct 132 ms 221932 KB Output is correct
3 Correct 134 ms 221932 KB Output is correct
4 Correct 131 ms 221932 KB Output is correct
5 Correct 136 ms 222060 KB Output is correct
6 Correct 133 ms 222060 KB Output is correct
7 Correct 133 ms 222060 KB Output is correct
8 Correct 135 ms 222060 KB Output is correct
9 Correct 132 ms 221932 KB Output is correct
10 Correct 134 ms 221932 KB Output is correct
11 Correct 133 ms 222264 KB Output is correct
12 Correct 135 ms 222132 KB Output is correct
13 Correct 134 ms 222316 KB Output is correct
14 Correct 134 ms 222316 KB Output is correct
15 Correct 136 ms 222316 KB Output is correct
16 Correct 466 ms 254444 KB Output is correct
17 Correct 466 ms 254432 KB Output is correct
18 Correct 480 ms 254572 KB Output is correct
19 Correct 452 ms 254444 KB Output is correct
20 Correct 448 ms 254504 KB Output is correct

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 222008 KB Output is correct
2 Correct 132 ms 221932 KB Output is correct
3 Correct 134 ms 221932 KB Output is correct
4 Correct 131 ms 221932 KB Output is correct
5 Correct 136 ms 222060 KB Output is correct
6 Correct 133 ms 222060 KB Output is correct
7 Correct 133 ms 222060 KB Output is correct
8 Correct 135 ms 222060 KB Output is correct
9 Correct 132 ms 221932 KB Output is correct
10 Correct 134 ms 221932 KB Output is correct
11 Correct 133 ms 222264 KB Output is correct
12 Correct 135 ms 222132 KB Output is correct
13 Correct 134 ms 222316 KB Output is correct
14 Correct 134 ms 222316 KB Output is correct
15 Correct 136 ms 222316 KB Output is correct
16 Correct 466 ms 254444 KB Output is correct
17 Correct 466 ms 254432 KB Output is correct
18 Correct 480 ms 254572 KB Output is correct
19 Correct 452 ms 254444 KB Output is correct
20 Correct 448 ms 254504 KB Output is correct
21 Runtime error 227 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -