oj.uz

Submission #391922

# Submission time Handle Problem Language Result Execution time Memory
391922 2021-04-20T07:36:33 Z BartolM Bootfall (IZhO17_bootfall) C++17
44 / 100
 1000 ms 1092 KB 
#define DEBUG 1
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=505;

int n, uk=0;
int p[N], cnt[N*N];
vector <int> sol;
bitset <N*N> curr;

void resi(int ne) {
    curr.reset();
    curr.set(0);
    for (int i=0; i<n; ++i) {
        if (i==ne) continue;
        curr=curr | (curr<<p[i]);
    }
}

void solve() {
    resi(n);
    if (!curr[uk/2]) {
        printf("0\n");
        return;
    }
    for (int i=0; i<n; ++i) {
        resi(i);
        for (int j=0; j<=uk; ++j) {
            int br=p[i]+2*j-uk;
            if (br>=0 && br<=uk && curr[j]) cnt[br]++;
        }
    }
    for (int i=0; i<=uk; ++i) if (cnt[i]==n) sol.pb(i);
    printf("%d\n", sol.size());
    for (int x:sol) printf("%d ", x);
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i) scanf("%d", p+i);
    for (int i=0; i<n; ++i) uk+=p[i];
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message

bootfall.cpp: In function 'void solve()':
bootfall.cpp:47:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   47 |     printf("%d\n", sol.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<int>::size_type {aka long unsigned int}
      |             %ld
bootfall.cpp: In function 'void load()':
bootfall.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
bootfall.cpp:53:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     for (int i=0; i<n; ++i) scanf("%d", p+i);
      |                             ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 11 ms 332 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 8 ms 312 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Correct 11 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 9 ms 332 KB Output is correct
19 Correct 8 ms 332 KB Output is correct
20 Correct 11 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 11 ms 332 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 8 ms 312 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Correct 11 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 9 ms 332 KB Output is correct
19 Correct 8 ms 332 KB Output is correct
20 Correct 11 ms 332 KB Output is correct
21 Correct 46 ms 388 KB Output is correct
22 Correct 63 ms 332 KB Output is correct
23 Correct 30 ms 400 KB Output is correct
24 Correct 116 ms 400 KB Output is correct
25 Correct 102 ms 424 KB Output is correct
26 Correct 123 ms 408 KB Output is correct
27 Correct 110 ms 412 KB Output is correct
28 Correct 114 ms 332 KB Output is correct
29 Correct 113 ms 424 KB Output is correct
30 Correct 111 ms 400 KB Output is correct
31 Correct 116 ms 396 KB Output is correct
32 Correct 137 ms 428 KB Output is correct
33 Correct 116 ms 412 KB Output is correct
34 Correct 117 ms 412 KB Output is correct
35 Correct 156 ms 416 KB Output is correct
36 Correct 112 ms 392 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 11 ms 332 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 8 ms 312 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Correct 11 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 9 ms 332 KB Output is correct
19 Correct 8 ms 332 KB Output is correct
20 Correct 11 ms 332 KB Output is correct
21 Correct 46 ms 388 KB Output is correct
22 Correct 63 ms 332 KB Output is correct
23 Correct 30 ms 400 KB Output is correct
24 Correct 116 ms 400 KB Output is correct
25 Correct 102 ms 424 KB Output is correct
26 Correct 123 ms 408 KB Output is correct
27 Correct 110 ms 412 KB Output is correct
28 Correct 114 ms 332 KB Output is correct
29 Correct 113 ms 424 KB Output is correct
30 Correct 111 ms 400 KB Output is correct
31 Correct 116 ms 396 KB Output is correct
32 Correct 137 ms 428 KB Output is correct
33 Correct 116 ms 412 KB Output is correct
34 Correct 117 ms 412 KB Output is correct
35 Correct 156 ms 416 KB Output is correct
36 Correct 112 ms 392 KB Output is correct
37 Correct 505 ms 580 KB Output is correct
38 Correct 448 ms 580 KB Output is correct
39 Correct 705 ms 620 KB Output is correct
40 Correct 836 ms 644 KB Output is correct
41 Correct 835 ms 668 KB Output is correct
42 Correct 701 ms 628 KB Output is correct
43 Correct 731 ms 1092 KB Output is correct
44 Correct 746 ms 1092 KB Output is correct
45 Correct 716 ms 1000 KB Output is correct
46 Correct 840 ms 500 KB Output is correct
47 Correct 696 ms 628 KB Output is correct
48 Correct 720 ms 836 KB Output is correct
49 Correct 769 ms 620 KB Output is correct
50 Correct 707 ms 632 KB Output is correct
51 Correct 709 ms 500 KB Output is correct
52 Correct 842 ms 1032 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 11 ms 332 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 8 ms 312 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Correct 11 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 9 ms 332 KB Output is correct
19 Correct 8 ms 332 KB Output is correct
20 Correct 11 ms 332 KB Output is correct
21 Correct 46 ms 388 KB Output is correct
22 Correct 63 ms 332 KB Output is correct
23 Correct 30 ms 400 KB Output is correct
24 Correct 116 ms 400 KB Output is correct
25 Correct 102 ms 424 KB Output is correct
26 Correct 123 ms 408 KB Output is correct
27 Correct 110 ms 412 KB Output is correct
28 Correct 114 ms 332 KB Output is correct
29 Correct 113 ms 424 KB Output is correct
30 Correct 111 ms 400 KB Output is correct
31 Correct 116 ms 396 KB Output is correct
32 Correct 137 ms 428 KB Output is correct
33 Correct 116 ms 412 KB Output is correct
34 Correct 117 ms 412 KB Output is correct
35 Correct 156 ms 416 KB Output is correct
36 Correct 112 ms 392 KB Output is correct
37 Correct 505 ms 580 KB Output is correct
38 Correct 448 ms 580 KB Output is correct
39 Correct 705 ms 620 KB Output is correct
40 Correct 836 ms 644 KB Output is correct
41 Correct 835 ms 668 KB Output is correct
42 Correct 701 ms 628 KB Output is correct
43 Correct 731 ms 1092 KB Output is correct
44 Correct 746 ms 1092 KB Output is correct
45 Correct 716 ms 1000 KB Output is correct
46 Correct 840 ms 500 KB Output is correct
47 Correct 696 ms 628 KB Output is correct
48 Correct 720 ms 836 KB Output is correct
49 Correct 769 ms 620 KB Output is correct
50 Correct 707 ms 632 KB Output is correct
51 Correct 709 ms 500 KB Output is correct
52 Correct 842 ms 1032 KB Output is correct
53 Execution timed out 1016 ms 812 KB Time limit exceeded
54 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 11 ms 332 KB Output is correct
12 Correct 11 ms 332 KB Output is correct
13 Correct 8 ms 312 KB Output is correct
14 Correct 10 ms 332 KB Output is correct
15 Correct 9 ms 332 KB Output is correct
16 Correct 11 ms 332 KB Output is correct
17 Correct 4 ms 332 KB Output is correct
18 Correct 9 ms 332 KB Output is correct
19 Correct 8 ms 332 KB Output is correct
20 Correct 11 ms 332 KB Output is correct
21 Correct 46 ms 388 KB Output is correct
22 Correct 63 ms 332 KB Output is correct
23 Correct 30 ms 400 KB Output is correct
24 Correct 116 ms 400 KB Output is correct
25 Correct 102 ms 424 KB Output is correct
26 Correct 123 ms 408 KB Output is correct
27 Correct 110 ms 412 KB Output is correct
28 Correct 114 ms 332 KB Output is correct
29 Correct 113 ms 424 KB Output is correct
30 Correct 111 ms 400 KB Output is correct
31 Correct 116 ms 396 KB Output is correct
32 Correct 137 ms 428 KB Output is correct
33 Correct 116 ms 412 KB Output is correct
34 Correct 117 ms 412 KB Output is correct
35 Correct 156 ms 416 KB Output is correct
36 Correct 112 ms 392 KB Output is correct
37 Correct 505 ms 580 KB Output is correct
38 Correct 448 ms 580 KB Output is correct
39 Correct 705 ms 620 KB Output is correct
40 Correct 836 ms 644 KB Output is correct
41 Correct 835 ms 668 KB Output is correct
42 Correct 701 ms 628 KB Output is correct
43 Correct 731 ms 1092 KB Output is correct
44 Correct 746 ms 1092 KB Output is correct
45 Correct 716 ms 1000 KB Output is correct
46 Correct 840 ms 500 KB Output is correct
47 Correct 696 ms 628 KB Output is correct
48 Correct 720 ms 836 KB Output is correct
49 Correct 769 ms 620 KB Output is correct
50 Correct 707 ms 632 KB Output is correct
51 Correct 709 ms 500 KB Output is correct
52 Correct 842 ms 1032 KB Output is correct
53 Execution timed out 1016 ms 812 KB Time limit exceeded
54 Halted 0 ms 0 KB -