oj.uz

Submission #322220

# Submission time Handle Problem Language Result Execution time Memory
322220 2020-11-14T09:39:27 Z dolphingarlic Swap (BOI16_swap) C++14
48 / 100
 275 ms 262148 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int a[1 << 18];
vector<int> dp[1 << 18][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 125 ms 209644 KB Output is correct
2 Correct 125 ms 209644 KB Output is correct
3 Correct 124 ms 209644 KB Output is correct
4 Correct 127 ms 209772 KB Output is correct
5 Correct 127 ms 209644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209644 KB Output is correct
2 Correct 125 ms 209644 KB Output is correct
3 Correct 124 ms 209644 KB Output is correct
4 Correct 127 ms 209772 KB Output is correct
5 Correct 127 ms 209644 KB Output is correct
6 Correct 126 ms 209644 KB Output is correct
7 Correct 126 ms 209772 KB Output is correct
8 Correct 125 ms 209644 KB Output is correct
9 Correct 126 ms 209644 KB Output is correct
10 Correct 125 ms 209772 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209644 KB Output is correct
2 Correct 125 ms 209644 KB Output is correct
3 Correct 124 ms 209644 KB Output is correct
4 Correct 127 ms 209772 KB Output is correct
5 Correct 127 ms 209644 KB Output is correct
6 Correct 126 ms 209644 KB Output is correct
7 Correct 126 ms 209772 KB Output is correct
8 Correct 125 ms 209644 KB Output is correct
9 Correct 126 ms 209644 KB Output is correct
10 Correct 125 ms 209772 KB Output is correct
11 Correct 130 ms 210412 KB Output is correct
12 Correct 129 ms 210412 KB Output is correct
13 Correct 131 ms 210412 KB Output is correct
14 Correct 128 ms 210412 KB Output is correct
15 Correct 129 ms 210412 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209644 KB Output is correct
2 Correct 125 ms 209644 KB Output is correct
3 Correct 124 ms 209644 KB Output is correct
4 Correct 127 ms 209772 KB Output is correct
5 Correct 127 ms 209644 KB Output is correct
6 Correct 126 ms 209644 KB Output is correct
7 Correct 126 ms 209772 KB Output is correct
8 Correct 125 ms 209644 KB Output is correct
9 Correct 126 ms 209644 KB Output is correct
10 Correct 125 ms 209772 KB Output is correct
11 Correct 130 ms 210412 KB Output is correct
12 Correct 129 ms 210412 KB Output is correct
13 Correct 131 ms 210412 KB Output is correct
14 Correct 128 ms 210412 KB Output is correct
15 Correct 129 ms 210412 KB Output is correct
16 Runtime error 275 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 209644 KB Output is correct
2 Correct 125 ms 209644 KB Output is correct
3 Correct 124 ms 209644 KB Output is correct
4 Correct 127 ms 209772 KB Output is correct
5 Correct 127 ms 209644 KB Output is correct
6 Correct 126 ms 209644 KB Output is correct
7 Correct 126 ms 209772 KB Output is correct
8 Correct 125 ms 209644 KB Output is correct
9 Correct 126 ms 209644 KB Output is correct
10 Correct 125 ms 209772 KB Output is correct
11 Correct 130 ms 210412 KB Output is correct
12 Correct 129 ms 210412 KB Output is correct
13 Correct 131 ms 210412 KB Output is correct
14 Correct 128 ms 210412 KB Output is correct
15 Correct 129 ms 210412 KB Output is correct
16 Runtime error 275 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -