CSES - IZhO 2017, day 1 - Results
Submission details
Task:Bootfall
Sender:henrikaalto
Submission time:2019-03-10 00:03:59 +0200
Language:C++
Status:READY
Result:13
Feedback
groupverdictscore
#1ACCEPTED6
#2ACCEPTED7
#30
#40
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.02 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.04 s1details
#7ACCEPTED0.02 s1details
#8ACCEPTED0.04 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.04 s2details
#11ACCEPTED0.06 s2details
#12ACCEPTED0.06 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.05 s2details
#15ACCEPTED0.04 s2details
#16ACCEPTED0.05 s2details
#17ACCEPTED0.05 s2details
#18ACCEPTED0.04 s2details
#19ACCEPTED0.04 s2details
#20ACCEPTED0.04 s2details
#210.07 s3details
#220.07 s3details
#230.07 s3details
#240.08 s3details
#250.09 s3details
#260.11 s3details
#270.09 s3details
#280.09 s3details
#290.10 s3details
#30ACCEPTED0.10 s3details
#310.10 s3details
#320.10 s3details
#330.09 s3details
#340.09 s3details
#350.10 s3details
#360.09 s3details
#370.18 s4details
#380.19 s4details
#390.20 s4details
#400.26 s4details
#410.20 s4details
#420.24 s4details
#430.27 s4details
#440.28 s4details
#450.29 s4details
#46ACCEPTED0.23 s4details
#470.26 s4details
#480.28 s4details
#490.24 s4details
#500.25 s4details
#51ACCEPTED0.25 s4details
#520.33 s4details
#530.32 s5details
#540.40 s5details
#550.52 s5details
#560.36 s5details
#570.53 s5details
#580.41 s5details
#590.45 s5details
#60ACCEPTED0.41 s5details
#610.47 s5details
#620.45 s5details
#630.46 s5details
#640.46 s5details
#650.24 s5details
#660.25 s5details
#670.52 s6details
#68ACCEPTED0.10 s6details
#69--6details
#700.82 s6details
#710.81 s6details
#72ACCEPTED0.81 s6details
#73ACCEPTED0.81 s6details
#74--6details
#750.98 s6details
#76--6details
#77--6details

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 250000;
int d[N+1];
int p[N+1];
 
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  p[0] = 1;
  int s = 0;
  for(int i = 1; i <= n; i++) {
    cin >> d[i];
    s += d[i];
    for(int x = N-d[i]; x>=0; --x) {
      p[x+d[i]] += p[x];
    }
  }
  if(!p[s/2]) return cout << 0,0;
  bitset<N+1> bt;
  bt.flip();
  for(int i=1;i<=n;i++) {  
    for(int x = 0; x <= N-d[i]; x++) {
      p[x+d[i]] -= p[x];
    }
    int o = s - d[i];
    bitset<N+1> tb;
    for(int x = 0; x <= N; x++)
      if(0<p[x]) {
        int y = abs(o - x);
        int z = abs(o-y);
        tb[abs(y-z)] = 1;
      }
    bt &= tb;
    for(int x = N-d[i]; x>=0; --x) {
      p[x+d[i]] += p[x];
    }
  }
  int l = 0;
  for(int i=1;i<N;i++)
    if(bt[i]) {
      l++;
    }
  cout << l << "\n";
  for(int i=1;i<N;i++)
    if(bt[i]) cout << i << " ";
  cout << "\n";
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
4
1 3 1 5

correct output
1

user output
1

Test 2

Group: 1

Verdict: ACCEPTED

input
6
3 5 7 11 9 13

correct output
4
1 3 17 19 

user output
4
1 3 17 19 

Test 3

Group: 1

Verdict: ACCEPTED

input
3
2 2 2

correct output
0

user output
0

Test 4

Group: 1

Verdict: ACCEPTED

input
4
200 200 200 200

correct output
2
200 600 

user output
2
200 600 

Test 5

Group: 1

Verdict: ACCEPTED

input
12
51 45 111 103 155 59 35 11 75 ...

correct output
122
3 5 13 15 19 21 27 29 31 33 37...

user output
122
3 5 13 15 19 21 27 29 31 33 37...
Truncated

Test 6

Group: 1

Verdict: ACCEPTED

input
8
11 13 31 23 51 11 45 13

correct output
3
33 39 51 

user output
3
33 39 51 

Test 7

Group: 1

Verdict: ACCEPTED

input
6
77 21 35 49 91 49

correct output
1
133 

user output
1
133 

Test 8

Group: 1

Verdict: ACCEPTED

input
12
150 190 138 198 198 66 126 10 ...

correct output
140
2 6 10 14 18 22 26 30 34 38 42...

user output
140
2 6 10 14 18 22 26 30 34 38 42...
Truncated

Test 9

Group: 1

Verdict: ACCEPTED

input
10
32 71 89 38 82 36 16 84 69 33

correct output
0

user output
0

Test 10

Group: 2

Verdict: ACCEPTED

input
30
19 19 19 19 19 19 19 19 19 19 ...

correct output
15
19 57 95 133 171 209 247 285 3...

user output
15
19 57 95 133 171 209 247 285 3...

Test 11

Group: 2

Verdict: ACCEPTED

input
30
3 15 11 3 3 17 9 9 1 17 5 15 1...

correct output
118
1 3 5 7 9 11 13 15 17 19 21 23...

user output
118
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 12

Group: 2

Verdict: ACCEPTED

input
30
18 20 12 16 18 6 2 4 14 16 12 ...

correct output
0

user output
0

Test 13

Group: 2

Verdict: ACCEPTED

input
26
6 20 5 7 4 11 16 7 1 15 10 9 1...

correct output
0

user output
0

Test 14

Group: 2

Verdict: ACCEPTED

input
28
17 15 5 7 5 15 19 3 9 5 15 15 ...

correct output
135
1 3 5 7 9 11 13 15 17 19 21 23...

user output
135
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 15

Group: 2

Verdict: ACCEPTED

input
28
3 3 5 3 5 1 19 3 5 9 3 1 9 9 1...

correct output
101
1 3 5 7 9 11 13 15 17 19 21 23...

user output
101
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 16

Group: 2

Verdict: ACCEPTED

input
30
3 3 13 13 1 7 1 7 9 3 7 19 1 3...

correct output
117
1 3 5 7 9 11 13 15 17 19 21 23...

user output
117
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 17

Group: 2

Verdict: ACCEPTED

input
18
9 5 5 19 19 13 13 3 1 19 5 3 7...

correct output
81
1 3 5 7 9 11 13 15 17 19 21 23...

user output
81
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 18

Group: 2

Verdict: ACCEPTED

input
24
17 5 1 9 7 13 17 7 17 7 9 13 1...

correct output
112
1 3 5 7 9 11 13 15 17 19 21 23...

user output
112
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 19

Group: 2

Verdict: ACCEPTED

input
26
17 13 9 9 19 3 5 3 7 5 9 5 7 7...

correct output
87
1 3 5 7 9 11 13 15 17 19 21 23...

user output
87
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 20

Group: 2

Verdict: ACCEPTED

input
30
20 20 20 20 20 20 20 20 20 20 ...

correct output
15
20 60 100 140 180 220 260 300 ...

user output
15
20 60 100 140 180 220 260 300 ...

Test 21

Group: 3

Verdict:

input
64
61 65 13 49 83 3 71 87 45 39 2...

correct output
1523
1 3 5 7 9 11 13 15 17 19 21 23...

user output
331
2385 2387 2389 2391 2393 2395 ...
Truncated

Test 22

Group: 3

Verdict:

input
74
93 69 63 89 13 85 47 65 23 13 ...

correct output
1656
1 3 5 7 9 11 13 15 17 19 21 23...

user output
256
2801 2803 2805 2807 2809 2811 ...
Truncated

Test 23

Group: 3

Verdict:

input
50
11 27 27 95 49 49 27 27 41 63 ...

correct output
1113
1 3 5 7 9 11 13 15 17 19 21 23...

user output
465
373 375 377 379 1199 1201 1203...
Truncated

Test 24

Group: 3

Verdict:

input
94
27 41 75 17 25 63 85 29 1 83 3...

correct output
2252
1 3 5 7 9 11 13 15 17 19 21 23...

user output
194
4117 4119 4121 4123 4125 4127 ...
Truncated

Test 25

Group: 3

Verdict:

input
94
99 99 97 97 95 95 89 97 91 95 ...

correct output
2952
1 3 5 7 9 11 13 15 17 19 21 23...

user output
104
247 463 473 671 857 879 1023 1...
Truncated

Test 26

Group: 3

Verdict:

input
100
91 95 89 89 93 95 97 95 99 95 ...

correct output
3239
1 3 5 7 9 11 13 15 17 19 21 23...

user output
92
101 187 431 673 803 951 1157 1...
Truncated

Test 27

Group: 3

Verdict:

input
100
90 90 90 82 90 90 98 78 78 98 ...

correct output
1892
2 6 10 14 18 22 26 30 34 38 42...

user output
90
182 394 646 730 838 950 1074 1...
Truncated

Test 28

Group: 3

Verdict:

input
100
98 98 94 98 98 94 90 98 90 98 ...

correct output
1516
2 6 10 14 18 22 26 30 34 38 42...

user output
223
22 78 162 238 262 282 370 398 ...
Truncated

Test 29

Group: 3

Verdict:

input
100
99 97 99 99 95 99 97 99 95 97 ...

correct output
840
1 3 5 7 9 11 13 15 17 19 21 23...

user output
147
3 35 41 163 165 209 211 349 35...
Truncated

Test 30

Group: 3

Verdict: ACCEPTED

input
100
13 49 3 89 88 49 58 31 68 19 4...

correct output
0

user output
0

Test 31

Group: 3

Verdict:

input
100
59 55 69 93 77 87 95 89 85 55 ...

correct output
3535
1 3 5 7 9 11 13 15 17 19 21 23...

user output
363
6345 6347 6349 6351 6353 6355 ...
Truncated

Test 32

Group: 3

Verdict:

input
100
99 35 99 35 25 3 29 49 93 47 5...

correct output
2320
1 3 5 7 9 11 13 15 17 19 21 23...

user output
175
4291 4293 4295 4297 4299 4301 ...
Truncated

Test 33

Group: 3

Verdict:

input
100
100 100 100 100 100 100 100 10...

correct output
50
100 300 500 700 900 1100 1300 ...

user output
24
900 2100 2300 3100 3700 4300 4...
Truncated

Test 34

Group: 3

Verdict:

input
100
99 99 99 99 99 99 99 99 99 99 ...

correct output
50
99 297 495 693 891 1089 1287 1...

user output
24
891 2079 2277 3069 3663 4257 4...
Truncated

Test 35

Group: 3

Verdict:

input
100
97 97 95 97 97 95 97 97 95 97 ...

correct output
196
1 3 5 7 187 189 191 193 195 19...

user output
56
191 577 769 1167 1171 1361 213...
Truncated

Test 36

Group: 3

Verdict:

input
100
89 45 21 35 5 43 1 35 53 89 9 ...

correct output
2285
1 3 5 7 9 11 13 15 17 19 21 23...

user output
148
4275 4277 4279 4281 4283 4285 ...
Truncated

Test 37

Group: 4

Verdict:

input
200
135 105 103 137 51 61 117 69 1...

correct output
9478
1 3 5 7 9 11 13 15 17 19 21 23...

user output
323
18311 18313 18315 18317 18319 ...
Truncated

Test 38

Group: 4

Verdict:

input
200
147 135 79 131 121 97 149 83 8...

correct output
9770
1 3 5 7 9 11 13 15 17 19 21 23...

user output
382
18777 18779 18781 18783 18785 ...
Truncated

Test 39

Group: 4

Verdict:

input
248
249 249 249 249 249 249 249 24...

correct output
124
249 747 1245 1743 2241 2739 32...

user output
72
2241 3237 4233 4731 6225 7221 ...
Truncated

Test 40

Group: 4

Verdict:

input
270
137 87 235 239 165 269 15 201 ...

correct output
16063
1 3 5 7 9 11 13 15 17 19 21 23...

user output
94
31939 31941 31943 31945 31947 ...
Truncated

Test 41

Group: 4

Verdict:

input
270
270 270 270 270 270 270 270 27...

correct output
135
270 810 1350 1890 2430 2970 35...

user output
67
810 2430 4050 5130 5670 6210 6...
Truncated

Test 42

Group: 4

Verdict:

input
250
71 79 29 83 87 161 171 43 43 5...

correct output
14889
1 3 5 7 9 11 13 15 17 19 21 23...

user output
72
29635 29637 29639 29641 29643 ...
Truncated

Test 43

Group: 4

Verdict:

input
244
217 211 209 207 223 241 245 20...

correct output
25704
1 3 5 7 9 11 13 15 17 19 21 23...

user output
53
51873 51875 51877 51879 51881 ...
Truncated

Test 44

Group: 4

Verdict:

input
248
205 233 215 221 213 229 249 23...

correct output
26260
1 3 5 7 9 11 13 15 17 19 21 23...

user output
58
52957 52959 52961 52963 52965 ...
Truncated

Test 45

Group: 4

Verdict:

input
250
215 219 213 205 211 243 239 23...

correct output
26502
1 3 5 7 9 11 13 15 17 19 21 23...

user output
59
53423 53425 53427 53429 53431 ...
Truncated

Test 46

Group: 4

Verdict: ACCEPTED

input
270
42 178 50 198 148 4 98 152 172...

correct output
0

user output
0

Test 47

Group: 4

Verdict:

input
250
167 123 213 69 201 197 153 73 ...

correct output
16136
1 3 5 7 9 11 13 15 17 19 21 23...

user output
165
31943 31945 31947 31949 31951 ...
Truncated

Test 48

Group: 4

Verdict:

input
250
241 249 249 245 245 249 243 24...

correct output
18952
1 3 5 7 9 11 13 15 17 19 21 23...

user output
616
33 77 89 167 191 231 269 325 3...
Truncated

Test 49

Group: 4

Verdict:

input
250
245 247 249 245 245 249 249 24...

correct output
4793
1 3 5 7 9 11 13 15 17 19 21 23...

user output
640
21 35 37 105 397 409 425 443 4...
Truncated

Test 50

Group: 4

Verdict:

input
250
137 79 63 203 137 199 103 141 ...

correct output
16242
1 3 5 7 9 11 13 15 17 19 21 23...

user output
132
32221 32223 32225 32227 32229 ...
Truncated

Test 51

Group: 4

Verdict: ACCEPTED

input
250
25 114 237 180 130 177 162 118...

correct output
0

user output
0

Test 52

Group: 4

Verdict:

input
270
253 267 263 257 267 265 263 26...

correct output
29010
1 3 5 7 9 11 13 15 17 19 21 23...

user output
14
2073 5709 6275 6687 23031 2352...

Test 53

Group: 5

Verdict:

input
300
169 137 45 201 181 93 49 97 27...

correct output
22553
1 3 5 7 9 11 13 15 17 19 21 23...

user output
229
44649 44651 44653 44655 44657 ...
Truncated

Test 54

Group: 5

Verdict:

input
350
193 179 173 205 265 87 29 243 ...

correct output
27543
1 3 5 7 9 11 13 15 17 19 21 23...

user output
287
54513 54515 54517 54519 54521 ...
Truncated

Test 55

Group: 5

Verdict:

input
350
305 309 315 317 319 317 307 31...

correct output
48733
1 3 5 7 9 11 13 15 17 19 21 23...

user output
9
15071 17737 29119 35893 65351 ...

Test 56

Group: 5

Verdict:

input
306
147 107 247 213 253 265 37 45 ...

correct output
27574
1 3 5 7 9 11 13 15 17 19 21 23...

user output
276
54597 54599 54601 54603 54605 ...
Truncated

Test 57

Group: 5

Verdict:

input
350
347 349 325 333 345 335 321 33...

correct output
52392
1 3 5 7 9 11 13 15 17 19 21 23...

user output
0

Test 58

Group: 5

Verdict:

input
350
79 335 175 171 307 239 63 3 21...

correct output
30384
1 3 5 7 9 11 13 15 17 19 21 23...

user output
78
60613 60615 60617 60619 60621 ...
Truncated

Test 59

Group: 5

Verdict:

input
350
185 283 157 199 195 123 127 18...

correct output
37688
1 3 5 7 9 11 13 15 17 19 21 23...

user output
582
74213 74215 74217 74219 74221 ...
Truncated

Test 60

Group: 5

Verdict: ACCEPTED

input
350
57 19 32 305 10 45 60 82 104 1...

correct output
0

user output
0

Test 61

Group: 5

Verdict:

input
350
279 153 293 183 309 273 319 24...

correct output
42216
1 3 5 7 9 11 13 15 17 19 21 23...

user output
657
83119 83121 83123 83125 83127 ...
Truncated

Test 62

Group: 5

Verdict:

input
320
293 317 315 333 261 319 291 33...

correct output
46225
1 3 5 7 9 11 13 15 17 19 21 23...

user output
211
92131 92133 92135 92137 92139 ...
Truncated

Test 63

Group: 5

Verdict:

input
320
347 337 301 335 323 331 333 34...

correct output
48310
1 3 5 7 9 11 13 15 17 19 21 23...

user output
6
98553 98555 98557 98559 98561 ...

Test 64

Group: 5

Verdict:

input
314
333 321 321 335 335 315 303 30...

correct output
47592
1 3 5 7 9 11 13 15 17 19 21 23...

user output
10
97075 97077 97079 97081 97083 ...

Test 65

Group: 5

Verdict:

input
316
140 260 60 260 180 260 260 60 ...

correct output
1194
20 60 100 140 180 220 260 300 ...

user output
12
2060 24540 26780 39940 40780 4...

Test 66

Group: 5

Verdict:

input
310
145 195 285 235 265 245 75 195...

correct output
5275
5 15 25 35 45 55 65 75 85 95 1...

user output
8
52675 52685 52695 52705 52715 ...

Test 67

Group: 6

Verdict:

input
400
1 1 3 3 5 5 7 7 9 9 11 11 13 1...

correct output
39801
1 3 5 7 9 11 13 15 17 19 21 23...

user output
33
79537 79539 79541 79543 79545 ...
Truncated

Test 68

Group: 6

Verdict: ACCEPTED

input
500
196 402 352 58 462 284 162 108...

correct output
0

user output
0

Test 69

Group: 6

Verdict:

input
500
427 421 429 417 427 409 427 40...

correct output
100095
1 3 5 7 9 11 13 15 17 19 21 23...

user output
(empty)

Test 70

Group: 6

Verdict:

input
500
345 39 453 289 341 429 397 397...

correct output
63809
1 3 5 7 9 11 13 15 17 19 21 23...

user output
0

Test 71

Group: 6

Verdict:

input
500
161 357 285 223 269 155 483 29...

correct output
61840
1 3 5 7 9 11 13 15 17 19 21 23...

user output
17
123647 123649 123651 123653 12...
Truncated

Test 72

Group: 6

Verdict: ACCEPTED

input
500
97 221 235 16 407 43 33 454 47...

correct output
0

user output
0

Test 73

Group: 6

Verdict: ACCEPTED

input
499
499 362 138 107 439 227 296 34...

correct output
0

user output
0

Test 74

Group: 6

Verdict:

input
498
409 487 415 479 469 469 469 43...

correct output
108504
1 3 5 7 9 11 13 15 17 19 21 23...

user output
(empty)

Test 75

Group: 6

Verdict:

input
498
483 309 473 389 343 425 337 30...

correct output
86205
1 3 5 7 9 11 13 15 17 19 21 23...

user output
809
170793 170795 170797 170799 17...
Truncated

Test 76

Group: 6

Verdict:

input
500
495 491 497 483 497 487 489 49...

correct output
102728
1 3 5 7 9 11 13 15 17 19 21 23...

user output
(empty)

Test 77

Group: 6

Verdict:

input
500
479 471 455 455 467 461 469 44...

correct output
111377
1 3 5 7 9 11 13 15 17 19 21 23...

user output
(empty)