oj.uz

Submission #322208

# Submission time Handle Problem Language Result Execution time Memory
322208 2020-11-14T09:16:56 Z dolphingarlic Swap (BOI16_swap) C++14
68 / 100
 416 ms 209800 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int a[1 << 17];
vector<int> dp[1 << 17][17][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);
                }
            }
        }
    }

    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

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104940 KB Output is correct
2 Correct 63 ms 105068 KB Output is correct
3 Correct 64 ms 104940 KB Output is correct
4 Correct 63 ms 104940 KB Output is correct
5 Correct 63 ms 104940 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104940 KB Output is correct
2 Correct 63 ms 105068 KB Output is correct
3 Correct 64 ms 104940 KB Output is correct
4 Correct 63 ms 104940 KB Output is correct
5 Correct 63 ms 104940 KB Output is correct
6 Correct 62 ms 104940 KB Output is correct
7 Correct 68 ms 105068 KB Output is correct
8 Correct 62 ms 104940 KB Output is correct
9 Correct 64 ms 104940 KB Output is correct
10 Correct 63 ms 104960 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104940 KB Output is correct
2 Correct 63 ms 105068 KB Output is correct
3 Correct 64 ms 104940 KB Output is correct
4 Correct 63 ms 104940 KB Output is correct
5 Correct 63 ms 104940 KB Output is correct
6 Correct 62 ms 104940 KB Output is correct
7 Correct 68 ms 105068 KB Output is correct
8 Correct 62 ms 104940 KB Output is correct
9 Correct 64 ms 104940 KB Output is correct
10 Correct 63 ms 104960 KB Output is correct
11 Correct 65 ms 105708 KB Output is correct
12 Correct 64 ms 105836 KB Output is correct
13 Correct 65 ms 105708 KB Output is correct
14 Correct 65 ms 105964 KB Output is correct
15 Correct 67 ms 105708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104940 KB Output is correct
2 Correct 63 ms 105068 KB Output is correct
3 Correct 64 ms 104940 KB Output is correct
4 Correct 63 ms 104940 KB Output is correct
5 Correct 63 ms 104940 KB Output is correct
6 Correct 62 ms 104940 KB Output is correct
7 Correct 68 ms 105068 KB Output is correct
8 Correct 62 ms 104940 KB Output is correct
9 Correct 64 ms 104940 KB Output is correct
10 Correct 63 ms 104960 KB Output is correct
11 Correct 65 ms 105708 KB Output is correct
12 Correct 64 ms 105836 KB Output is correct
13 Correct 65 ms 105708 KB Output is correct
14 Correct 65 ms 105964 KB Output is correct
15 Correct 67 ms 105708 KB Output is correct
16 Correct 410 ms 209640 KB Output is correct
17 Correct 412 ms 209640 KB Output is correct
18 Correct 416 ms 209572 KB Output is correct
19 Correct 398 ms 209732 KB Output is correct
20 Correct 398 ms 209800 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 104940 KB Output is correct
2 Correct 63 ms 105068 KB Output is correct
3 Correct 64 ms 104940 KB Output is correct
4 Correct 63 ms 104940 KB Output is correct
5 Correct 63 ms 104940 KB Output is correct
6 Correct 62 ms 104940 KB Output is correct
7 Correct 68 ms 105068 KB Output is correct
8 Correct 62 ms 104940 KB Output is correct
9 Correct 64 ms 104940 KB Output is correct
10 Correct 63 ms 104960 KB Output is correct
11 Correct 65 ms 105708 KB Output is correct
12 Correct 64 ms 105836 KB Output is correct
13 Correct 65 ms 105708 KB Output is correct
14 Correct 65 ms 105964 KB Output is correct
15 Correct 67 ms 105708 KB Output is correct
16 Correct 410 ms 209640 KB Output is correct
17 Correct 412 ms 209640 KB Output is correct
18 Correct 416 ms 209572 KB Output is correct
19 Correct 398 ms 209732 KB Output is correct
20 Correct 398 ms 209800 KB Output is correct
21 Execution timed out 74 ms 106604 KB Time limit exceeded (wall clock)
22 Halted 0 ms 0 KB -