oj.uz

Submission #174659

# Submission time Handle Problem Language Result Execution time Memory
174659 2020-01-06T15:36:15 Z srvlt Bootfall (IZhO17_bootfall) C++14
100 / 100
 909 ms 5072 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;

#define ll long long
#define db double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

#define endl "\n"
//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 503, K = 250001;
const pii MOD = {1e9 + 7, 1e9 + 9};
int n, a[N], ans[K], res[K];
pii dp[K];

void add(pii & x, pii y) {
    x.fi += y.fi;
    if (x.fi >= MOD.fi) {
        x.fi -= MOD.fi;
    }
    x.se += y.se;
    if (x.se >= MOD.se) {
        x.se -= MOD.se;
    }
}

void sub(pii & x, pii y) {
    x.fi -= y.fi;
    if (x.fi < 0) {
        x.fi += MOD.fi;
    }
    x.se -= y.se;
    if (x.se < 0) {
        x.se += MOD.se;
    }
}

bool exist(int x) {
    return dp[x].fi > 0 || dp[x].se > 0;
}

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n;
    dp[0] = {1, 1};
    int total = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        total += a[i];
        for (int j = K - 1; j >= a[i]; j--) {
            add(dp[j], dp[j - a[i]]);
        }
    }
    if ((total & 1) || !exist(total >> 1)) {
        cout << 0;
        return;
    }
    fill(ans, ans + K, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j < K; j++) {
            sub(dp[j], dp[j - a[i]]);
        }
        total -= a[i];

        memset(res, 0, sizeof(res));
        for (int j = total & 1; j <= total; j += 2) {
            if (exist(total + j >> 1) || exist(total - j >> 1)) {
                res[j] = 1;
            }
        }
        for (int j = 0; j < K; j++) {
            ans[j] &= res[j];
        }
        memset(res, 0, sizeof(res));

        total += a[i];
        for (int j = K - 1; j >= a[i]; j--) {
            add(dp[j], dp[j - a[i]]);
        }
    }
    int cnt = 0;
    for (int i = 0; i < K; i++) {
        if (ans[i]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    for (int i = 0; i < K; i++) {
        if (ans[i]) {
            cout << i << " ";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Compilation message

bootfall.cpp: In function 'void solve(int)':
bootfall.cpp:93:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             if (exist(total + j >> 1) || exist(total - j >> 1)) {
                       ~~~~~~^~~
bootfall.cpp:93:54: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
             if (exist(total + j >> 1) || exist(total - j >> 1)) {
                                                ~~~~~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct
10 Correct 55 ms 4296 KB Output is correct
11 Correct 57 ms 4296 KB Output is correct
12 Correct 56 ms 4216 KB Output is correct
13 Correct 49 ms 4216 KB Output is correct
14 Correct 52 ms 4216 KB Output is correct
15 Correct 53 ms 4344 KB Output is correct
16 Correct 56 ms 4216 KB Output is correct
17 Correct 35 ms 4216 KB Output is correct
18 Correct 45 ms 4216 KB Output is correct
19 Correct 48 ms 4216 KB Output is correct
20 Correct 55 ms 4216 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct
10 Correct 55 ms 4296 KB Output is correct
11 Correct 57 ms 4296 KB Output is correct
12 Correct 56 ms 4216 KB Output is correct
13 Correct 49 ms 4216 KB Output is correct
14 Correct 52 ms 4216 KB Output is correct
15 Correct 53 ms 4344 KB Output is correct
16 Correct 56 ms 4216 KB Output is correct
17 Correct 35 ms 4216 KB Output is correct
18 Correct 45 ms 4216 KB Output is correct
19 Correct 48 ms 4216 KB Output is correct
20 Correct 55 ms 4216 KB Output is correct
21 Correct 111 ms 4372 KB Output is correct
22 Correct 127 ms 4308 KB Output is correct
23 Correct 88 ms 4304 KB Output is correct
24 Correct 166 ms 4216 KB Output is correct
25 Correct 158 ms 4328 KB Output is correct
26 Correct 169 ms 4348 KB Output is correct
27 Correct 172 ms 4344 KB Output is correct
28 Correct 168 ms 4216 KB Output is correct
29 Correct 171 ms 4372 KB Output is correct
30 Correct 167 ms 4216 KB Output is correct
31 Correct 169 ms 4344 KB Output is correct
32 Correct 168 ms 4344 KB Output is correct
33 Correct 168 ms 4436 KB Output is correct
34 Correct 169 ms 4392 KB Output is correct
35 Correct 168 ms 4408 KB Output is correct
36 Correct 171 ms 4344 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct
10 Correct 55 ms 4296 KB Output is correct
11 Correct 57 ms 4296 KB Output is correct
12 Correct 56 ms 4216 KB Output is correct
13 Correct 49 ms 4216 KB Output is correct
14 Correct 52 ms 4216 KB Output is correct
15 Correct 53 ms 4344 KB Output is correct
16 Correct 56 ms 4216 KB Output is correct
17 Correct 35 ms 4216 KB Output is correct
18 Correct 45 ms 4216 KB Output is correct
19 Correct 48 ms 4216 KB Output is correct
20 Correct 55 ms 4216 KB Output is correct
21 Correct 111 ms 4372 KB Output is correct
22 Correct 127 ms 4308 KB Output is correct
23 Correct 88 ms 4304 KB Output is correct
24 Correct 166 ms 4216 KB Output is correct
25 Correct 158 ms 4328 KB Output is correct
26 Correct 169 ms 4348 KB Output is correct
27 Correct 172 ms 4344 KB Output is correct
28 Correct 168 ms 4216 KB Output is correct
29 Correct 171 ms 4372 KB Output is correct
30 Correct 167 ms 4216 KB Output is correct
31 Correct 169 ms 4344 KB Output is correct
32 Correct 168 ms 4344 KB Output is correct
33 Correct 168 ms 4436 KB Output is correct
34 Correct 169 ms 4392 KB Output is correct
35 Correct 168 ms 4408 KB Output is correct
36 Correct 171 ms 4344 KB Output is correct
37 Correct 332 ms 4344 KB Output is correct
38 Correct 332 ms 4304 KB Output is correct
39 Correct 421 ms 4216 KB Output is correct
40 Correct 447 ms 4296 KB Output is correct
41 Correct 466 ms 4296 KB Output is correct
42 Correct 417 ms 4396 KB Output is correct
43 Correct 411 ms 4472 KB Output is correct
44 Correct 423 ms 4472 KB Output is correct
45 Correct 419 ms 4472 KB Output is correct
46 Correct 461 ms 4304 KB Output is correct
47 Correct 415 ms 4336 KB Output is correct
48 Correct 428 ms 4420 KB Output is correct
49 Correct 428 ms 4332 KB Output is correct
50 Correct 414 ms 4472 KB Output is correct
51 Correct 115 ms 2300 KB Output is correct
52 Correct 460 ms 4532 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct
10 Correct 55 ms 4296 KB Output is correct
11 Correct 57 ms 4296 KB Output is correct
12 Correct 56 ms 4216 KB Output is correct
13 Correct 49 ms 4216 KB Output is correct
14 Correct 52 ms 4216 KB Output is correct
15 Correct 53 ms 4344 KB Output is correct
16 Correct 56 ms 4216 KB Output is correct
17 Correct 35 ms 4216 KB Output is correct
18 Correct 45 ms 4216 KB Output is correct
19 Correct 48 ms 4216 KB Output is correct
20 Correct 55 ms 4216 KB Output is correct
21 Correct 111 ms 4372 KB Output is correct
22 Correct 127 ms 4308 KB Output is correct
23 Correct 88 ms 4304 KB Output is correct
24 Correct 166 ms 4216 KB Output is correct
25 Correct 158 ms 4328 KB Output is correct
26 Correct 169 ms 4348 KB Output is correct
27 Correct 172 ms 4344 KB Output is correct
28 Correct 168 ms 4216 KB Output is correct
29 Correct 171 ms 4372 KB Output is correct
30 Correct 167 ms 4216 KB Output is correct
31 Correct 169 ms 4344 KB Output is correct
32 Correct 168 ms 4344 KB Output is correct
33 Correct 168 ms 4436 KB Output is correct
34 Correct 169 ms 4392 KB Output is correct
35 Correct 168 ms 4408 KB Output is correct
36 Correct 171 ms 4344 KB Output is correct
37 Correct 332 ms 4344 KB Output is correct
38 Correct 332 ms 4304 KB Output is correct
39 Correct 421 ms 4216 KB Output is correct
40 Correct 447 ms 4296 KB Output is correct
41 Correct 466 ms 4296 KB Output is correct
42 Correct 417 ms 4396 KB Output is correct
43 Correct 411 ms 4472 KB Output is correct
44 Correct 423 ms 4472 KB Output is correct
45 Correct 419 ms 4472 KB Output is correct
46 Correct 461 ms 4304 KB Output is correct
47 Correct 415 ms 4336 KB Output is correct
48 Correct 428 ms 4420 KB Output is correct
49 Correct 428 ms 4332 KB Output is correct
50 Correct 414 ms 4472 KB Output is correct
51 Correct 115 ms 2300 KB Output is correct
52 Correct 460 ms 4532 KB Output is correct
53 Correct 503 ms 4424 KB Output is correct
54 Correct 585 ms 4472 KB Output is correct
55 Correct 598 ms 4728 KB Output is correct
56 Correct 526 ms 4392 KB Output is correct
57 Correct 612 ms 4588 KB Output is correct
58 Correct 583 ms 4472 KB Output is correct
59 Correct 586 ms 4500 KB Output is correct
60 Correct 157 ms 2296 KB Output is correct
61 Correct 589 ms 4476 KB Output is correct
62 Correct 538 ms 4688 KB Output is correct
63 Correct 546 ms 4628 KB Output is correct
64 Correct 532 ms 4600 KB Output is correct
65 Correct 531 ms 4344 KB Output is correct
66 Correct 525 ms 4372 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4216 KB Output is correct
2 Correct 16 ms 4344 KB Output is correct
3 Correct 6 ms 2300 KB Output is correct
4 Correct 13 ms 4216 KB Output is correct
5 Correct 26 ms 4216 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 16 ms 4296 KB Output is correct
8 Correct 26 ms 4216 KB Output is correct
9 Correct 22 ms 4216 KB Output is correct
10 Correct 55 ms 4296 KB Output is correct
11 Correct 57 ms 4296 KB Output is correct
12 Correct 56 ms 4216 KB Output is correct
13 Correct 49 ms 4216 KB Output is correct
14 Correct 52 ms 4216 KB Output is correct
15 Correct 53 ms 4344 KB Output is correct
16 Correct 56 ms 4216 KB Output is correct
17 Correct 35 ms 4216 KB Output is correct
18 Correct 45 ms 4216 KB Output is correct
19 Correct 48 ms 4216 KB Output is correct
20 Correct 55 ms 4216 KB Output is correct
21 Correct 111 ms 4372 KB Output is correct
22 Correct 127 ms 4308 KB Output is correct
23 Correct 88 ms 4304 KB Output is correct
24 Correct 166 ms 4216 KB Output is correct
25 Correct 158 ms 4328 KB Output is correct
26 Correct 169 ms 4348 KB Output is correct
27 Correct 172 ms 4344 KB Output is correct
28 Correct 168 ms 4216 KB Output is correct
29 Correct 171 ms 4372 KB Output is correct
30 Correct 167 ms 4216 KB Output is correct
31 Correct 169 ms 4344 KB Output is correct
32 Correct 168 ms 4344 KB Output is correct
33 Correct 168 ms 4436 KB Output is correct
34 Correct 169 ms 4392 KB Output is correct
35 Correct 168 ms 4408 KB Output is correct
36 Correct 171 ms 4344 KB Output is correct
37 Correct 332 ms 4344 KB Output is correct
38 Correct 332 ms 4304 KB Output is correct
39 Correct 421 ms 4216 KB Output is correct
40 Correct 447 ms 4296 KB Output is correct
41 Correct 466 ms 4296 KB Output is correct
42 Correct 417 ms 4396 KB Output is correct
43 Correct 411 ms 4472 KB Output is correct
44 Correct 423 ms 4472 KB Output is correct
45 Correct 419 ms 4472 KB Output is correct
46 Correct 461 ms 4304 KB Output is correct
47 Correct 415 ms 4336 KB Output is correct
48 Correct 428 ms 4420 KB Output is correct
49 Correct 428 ms 4332 KB Output is correct
50 Correct 414 ms 4472 KB Output is correct
51 Correct 115 ms 2300 KB Output is correct
52 Correct 460 ms 4532 KB Output is correct
53 Correct 503 ms 4424 KB Output is correct
54 Correct 585 ms 4472 KB Output is correct
55 Correct 598 ms 4728 KB Output is correct
56 Correct 526 ms 4392 KB Output is correct
57 Correct 612 ms 4588 KB Output is correct
58 Correct 583 ms 4472 KB Output is correct
59 Correct 586 ms 4500 KB Output is correct
60 Correct 157 ms 2296 KB Output is correct
61 Correct 589 ms 4476 KB Output is correct
62 Correct 538 ms 4688 KB Output is correct
63 Correct 546 ms 4628 KB Output is correct
64 Correct 532 ms 4600 KB Output is correct
65 Correct 531 ms 4344 KB Output is correct
66 Correct 525 ms 4372 KB Output is correct
67 Correct 672 ms 4560 KB Output is correct
68 Correct 223 ms 2344 KB Output is correct
69 Correct 890 ms 5040 KB Output is correct
70 Correct 862 ms 4784 KB Output is correct
71 Correct 855 ms 4628 KB Output is correct
72 Correct 853 ms 4344 KB Output is correct
73 Correct 852 ms 4372 KB Output is correct
74 Correct 888 ms 4984 KB Output is correct
75 Correct 867 ms 4884 KB Output is correct
76 Correct 909 ms 5012 KB Output is correct
77 Correct 895 ms 5072 KB Output is correct