CSES - IZhO 2017, day 1 - Results
Submission details
Task:Bootfall
Sender:henrikaalto
Submission time:2019-03-07 22:58:52 +0200
Language:C++
Status:READY
Result:94
Feedback
groupverdictscore
#10
#2ACCEPTED7
#3ACCEPTED15
#4ACCEPTED16
#5ACCEPTED21
#6ACCEPTED35
Test results
testverdicttimegroup
#1ACCEPTED0.03 s1details
#2ACCEPTED0.03 s1details
#30.02 s1details
#4ACCEPTED0.04 s1details
#5ACCEPTED0.04 s1details
#6ACCEPTED0.02 s1details
#7ACCEPTED0.03 s1details
#8ACCEPTED0.03 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.05 s2details
#11ACCEPTED0.06 s2details
#12ACCEPTED0.05 s2details
#13ACCEPTED0.05 s2details
#14ACCEPTED0.06 s2details
#15ACCEPTED0.06 s2details
#16ACCEPTED0.06 s2details
#17ACCEPTED0.04 s2details
#18ACCEPTED0.04 s2details
#19ACCEPTED0.05 s2details
#20ACCEPTED0.05 s2details
#21ACCEPTED0.07 s3details
#22ACCEPTED0.08 s3details
#23ACCEPTED0.06 s3details
#24ACCEPTED0.09 s3details
#25ACCEPTED0.09 s3details
#26ACCEPTED0.10 s3details
#27ACCEPTED0.10 s3details
#28ACCEPTED0.10 s3details
#29ACCEPTED0.11 s3details
#30ACCEPTED0.10 s3details
#31ACCEPTED0.10 s3details
#32ACCEPTED0.10 s3details
#33ACCEPTED0.10 s3details
#34ACCEPTED0.10 s3details
#35ACCEPTED0.10 s3details
#36ACCEPTED0.10 s3details
#37ACCEPTED0.18 s4details
#38ACCEPTED0.18 s4details
#39ACCEPTED0.20 s4details
#40ACCEPTED0.24 s4details
#41ACCEPTED0.22 s4details
#42ACCEPTED0.22 s4details
#43ACCEPTED0.24 s4details
#44ACCEPTED0.23 s4details
#45ACCEPTED0.24 s4details
#46ACCEPTED0.23 s4details
#47ACCEPTED0.22 s4details
#48ACCEPTED0.24 s4details
#49ACCEPTED0.23 s4details
#50ACCEPTED0.22 s4details
#51ACCEPTED0.22 s4details
#52ACCEPTED0.27 s4details
#53ACCEPTED0.28 s5details
#54ACCEPTED0.34 s5details
#55ACCEPTED0.37 s5details
#56ACCEPTED0.30 s5details
#57ACCEPTED0.39 s5details
#58ACCEPTED0.33 s5details
#59ACCEPTED0.34 s5details
#60ACCEPTED0.33 s5details
#61ACCEPTED0.35 s5details
#62ACCEPTED0.33 s5details
#63ACCEPTED0.34 s5details
#64ACCEPTED0.34 s5details
#65ACCEPTED0.27 s5details
#66ACCEPTED0.25 s5details
#67ACCEPTED0.40 s6details
#68ACCEPTED0.45 s6details
#69ACCEPTED0.65 s6details
#70ACCEPTED0.55 s6details
#71ACCEPTED0.56 s6details
#72ACCEPTED0.54 s6details
#73ACCEPTED0.55 s6details
#74ACCEPTED0.67 s6details
#75ACCEPTED0.61 s6details
#76ACCEPTED0.67 s6details
#77ACCEPTED0.68 s6details

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 250000;
int d[N+1];
// knapsack
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];
    }
  }
  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 = 1; x <= N; x++)
      if(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:

input
3
2 2 2

correct output
0

user output
1

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: ACCEPTED

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
1523
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 22

Group: 3

Verdict: ACCEPTED

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
1656
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 23

Group: 3

Verdict: ACCEPTED

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
1113
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 24

Group: 3

Verdict: ACCEPTED

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
2252
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 25

Group: 3

Verdict: ACCEPTED

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
2952
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 26

Group: 3

Verdict: ACCEPTED

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
3239
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 27

Group: 3

Verdict: ACCEPTED

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
1892
2 6 10 14 18 22 26 30 34 38 42...
Truncated

Test 28

Group: 3

Verdict: ACCEPTED

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
1516
2 6 10 14 18 22 26 30 34 38 42...
Truncated

Test 29

Group: 3

Verdict: ACCEPTED

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
840
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
3535
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 32

Group: 3

Verdict: ACCEPTED

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
2320
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 33

Group: 3

Verdict: ACCEPTED

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

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

user output
50
100 300 500 700 900 1100 1300 ...
Truncated

Test 34

Group: 3

Verdict: ACCEPTED

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
50
99 297 495 693 891 1089 1287 1...
Truncated

Test 35

Group: 3

Verdict: ACCEPTED

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
196
1 3 5 7 187 189 191 193 195 19...
Truncated

Test 36

Group: 3

Verdict: ACCEPTED

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
2285
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 37

Group: 4

Verdict: ACCEPTED

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
9478
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 38

Group: 4

Verdict: ACCEPTED

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
9770
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 39

Group: 4

Verdict: ACCEPTED

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

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

user output
124
249 747 1245 1743 2241 2739 32...
Truncated

Test 40

Group: 4

Verdict: ACCEPTED

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
16063
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 41

Group: 4

Verdict: ACCEPTED

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

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

user output
135
270 810 1350 1890 2430 2970 35...
Truncated

Test 42

Group: 4

Verdict: ACCEPTED

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
14889
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 43

Group: 4

Verdict: ACCEPTED

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
25704
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 44

Group: 4

Verdict: ACCEPTED

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
26260
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 45

Group: 4

Verdict: ACCEPTED

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
26502
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
16136
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 48

Group: 4

Verdict: ACCEPTED

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
18952
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 49

Group: 4

Verdict: ACCEPTED

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
4793
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 50

Group: 4

Verdict: ACCEPTED

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
16242
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
29010
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 53

Group: 5

Verdict: ACCEPTED

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
22553
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 54

Group: 5

Verdict: ACCEPTED

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
27543
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 55

Group: 5

Verdict: ACCEPTED

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
48733
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 56

Group: 5

Verdict: ACCEPTED

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
27574
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 57

Group: 5

Verdict: ACCEPTED

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
52392
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 58

Group: 5

Verdict: ACCEPTED

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
30384
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 59

Group: 5

Verdict: ACCEPTED

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
37688
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
42216
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 62

Group: 5

Verdict: ACCEPTED

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
46225
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 63

Group: 5

Verdict: ACCEPTED

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
48310
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 64

Group: 5

Verdict: ACCEPTED

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
47592
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 65

Group: 5

Verdict: ACCEPTED

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

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

user output
1194
20 60 100 140 180 220 260 300 ...
Truncated

Test 66

Group: 5

Verdict: ACCEPTED

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
5275
5 15 25 35 45 55 65 75 85 95 1...
Truncated

Test 67

Group: 6

Verdict: ACCEPTED

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
39801
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
100095
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 70

Group: 6

Verdict: ACCEPTED

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
63809
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 71

Group: 6

Verdict: ACCEPTED

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
61840
1 3 5 7 9 11 13 15 17 19 21 23...
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: ACCEPTED

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
108504
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 75

Group: 6

Verdict: ACCEPTED

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
86205
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 76

Group: 6

Verdict: ACCEPTED

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
102728
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated

Test 77

Group: 6

Verdict: ACCEPTED

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
111377
1 3 5 7 9 11 13 15 17 19 21 23...
Truncated