# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
41149 | 2018-02-13T06:28:26 Z | kriii | Snake Escaping (JOI18_snake_escaping) | C++14 | 1012 ms | 21820 KB |
#include <stdio.h> #include <algorithm> using namespace std; int L,Q; char sc[1<<20+2]; int bc[1<<20]; int Z[1<<20],O[1<<20]; void go(int l, int r) { if (l+1 == r) return; int m = (l + r) / 2; go(l,m); go(m,r); for (int i=l;i<m;i++){ Z[i-l+m] += Z[i]; O[i] += O[i-l+m]; } } int main() { scanf ("%d %d",&L,&Q); scanf ("%s",sc); for (int i=0;i<(1<<L);i++){ if (i) bc[i] = bc[i-(i&(-i))] + 1; Z[i] = O[i] = sc[i] - '0'; } go(0,(1<<L)); while (Q--){ char q[22]; scanf ("%s",q); int z = 0, o = 0, f = 0; for (int i=0;i<L;i++){ if (q[i] == '0') z |= 1 << (L - i - 1); if (q[i] == '1') o |= 1 << (L - i - 1); if (q[i] == '?') f |= 1 << (L - i - 1); } int m = min({bc[z],bc[o],bc[f]}); int ans = 0; if (bc[f] == m){ for (int x=f;;x=(x-1)&f){ ans += sc[x|o] - '0'; if (!x) break; } } else if (bc[o] == m){ for (int x=o;;x=(x-1)&o){ int b = f + x; if (bc[o] % 2 != bc[x] % 2) ans -= Z[b]; else ans += Z[b]; if (!x) break; } } else{ for (int x=z;;x=(x-1)&z){ int b = o + z - x; if (bc[z] % 2 != bc[x] % 2) ans -= O[b]; else ans += O[b]; if (!x) break; } } printf ("%d\n",ans); } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 2 ms | 560 KB | Output is correct |
7 | Correct | 2 ms | 560 KB | Output is correct |
8 | Correct | 1 ms | 560 KB | Output is correct |
9 | Correct | 2 ms | 560 KB | Output is correct |
10 | Correct | 2 ms | 560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 2 ms | 560 KB | Output is correct |
7 | Correct | 2 ms | 560 KB | Output is correct |
8 | Correct | 1 ms | 560 KB | Output is correct |
9 | Correct | 2 ms | 560 KB | Output is correct |
10 | Correct | 2 ms | 560 KB | Output is correct |
11 | Correct | 295 ms | 4588 KB | Output is correct |
12 | Correct | 296 ms | 4588 KB | Output is correct |
13 | Correct | 351 ms | 4588 KB | Output is correct |
14 | Correct | 297 ms | 4588 KB | Output is correct |
15 | Correct | 371 ms | 4588 KB | Output is correct |
16 | Correct | 321 ms | 4588 KB | Output is correct |
17 | Correct | 326 ms | 4588 KB | Output is correct |
18 | Correct | 223 ms | 5532 KB | Output is correct |
19 | Correct | 252 ms | 5532 KB | Output is correct |
20 | Correct | 289 ms | 5532 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 2 ms | 560 KB | Output is correct |
7 | Correct | 2 ms | 560 KB | Output is correct |
8 | Correct | 1 ms | 560 KB | Output is correct |
9 | Correct | 2 ms | 560 KB | Output is correct |
10 | Correct | 2 ms | 560 KB | Output is correct |
11 | Correct | 295 ms | 4588 KB | Output is correct |
12 | Correct | 296 ms | 4588 KB | Output is correct |
13 | Correct | 351 ms | 4588 KB | Output is correct |
14 | Correct | 297 ms | 4588 KB | Output is correct |
15 | Correct | 371 ms | 4588 KB | Output is correct |
16 | Correct | 321 ms | 4588 KB | Output is correct |
17 | Correct | 326 ms | 4588 KB | Output is correct |
18 | Correct | 223 ms | 5532 KB | Output is correct |
19 | Correct | 252 ms | 5532 KB | Output is correct |
20 | Correct | 289 ms | 5532 KB | Output is correct |
21 | Correct | 321 ms | 5532 KB | Output is correct |
22 | Correct | 329 ms | 5532 KB | Output is correct |
23 | Correct | 400 ms | 5532 KB | Output is correct |
24 | Correct | 379 ms | 5532 KB | Output is correct |
25 | Correct | 354 ms | 5664 KB | Output is correct |
26 | Correct | 388 ms | 5664 KB | Output is correct |
27 | Correct | 431 ms | 5664 KB | Output is correct |
28 | Correct | 245 ms | 6684 KB | Output is correct |
29 | Correct | 309 ms | 6684 KB | Output is correct |
30 | Correct | 330 ms | 6684 KB | Output is correct |
31 | Correct | 392 ms | 6684 KB | Output is correct |
32 | Correct | 395 ms | 6684 KB | Output is correct |
33 | Correct | 355 ms | 6684 KB | Output is correct |
34 | Correct | 419 ms | 6684 KB | Output is correct |
35 | Correct | 421 ms | 6684 KB | Output is correct |
36 | Correct | 239 ms | 6684 KB | Output is correct |
37 | Correct | 334 ms | 6684 KB | Output is correct |
38 | Correct | 346 ms | 6684 KB | Output is correct |
39 | Correct | 418 ms | 6684 KB | Output is correct |
40 | Correct | 397 ms | 6684 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 2 ms | 560 KB | Output is correct |
7 | Correct | 2 ms | 560 KB | Output is correct |
8 | Correct | 1 ms | 560 KB | Output is correct |
9 | Correct | 2 ms | 560 KB | Output is correct |
10 | Correct | 2 ms | 560 KB | Output is correct |
11 | Correct | 67 ms | 14236 KB | Output is correct |
12 | Correct | 71 ms | 14236 KB | Output is correct |
13 | Correct | 76 ms | 14364 KB | Output is correct |
14 | Correct | 76 ms | 14364 KB | Output is correct |
15 | Correct | 63 ms | 14364 KB | Output is correct |
16 | Correct | 79 ms | 14364 KB | Output is correct |
17 | Correct | 77 ms | 14364 KB | Output is correct |
18 | Correct | 53 ms | 14364 KB | Output is correct |
19 | Correct | 62 ms | 14364 KB | Output is correct |
20 | Correct | 66 ms | 14364 KB | Output is correct |
21 | Correct | 76 ms | 14364 KB | Output is correct |
22 | Correct | 77 ms | 14364 KB | Output is correct |
23 | Correct | 67 ms | 14364 KB | Output is correct |
24 | Correct | 77 ms | 14364 KB | Output is correct |
25 | Correct | 84 ms | 14364 KB | Output is correct |
26 | Correct | 51 ms | 14364 KB | Output is correct |
27 | Correct | 63 ms | 14364 KB | Output is correct |
28 | Correct | 67 ms | 14364 KB | Output is correct |
29 | Correct | 68 ms | 14364 KB | Output is correct |
30 | Correct | 71 ms | 14364 KB | Output is correct |
31 | Correct | 72 ms | 14364 KB | Output is correct |
32 | Correct | 101 ms | 14364 KB | Output is correct |
33 | Correct | 85 ms | 14364 KB | Output is correct |
34 | Correct | 54 ms | 14364 KB | Output is correct |
35 | Correct | 72 ms | 14364 KB | Output is correct |
36 | Correct | 85 ms | 14364 KB | Output is correct |
37 | Correct | 84 ms | 14364 KB | Output is correct |
38 | Correct | 75 ms | 14364 KB | Output is correct |
39 | Correct | 73 ms | 14364 KB | Output is correct |
40 | Correct | 75 ms | 14364 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 2 ms | 480 KB | Output is correct |
3 | Correct | 2 ms | 560 KB | Output is correct |
4 | Correct | 2 ms | 560 KB | Output is correct |
5 | Correct | 2 ms | 560 KB | Output is correct |
6 | Correct | 2 ms | 560 KB | Output is correct |
7 | Correct | 2 ms | 560 KB | Output is correct |
8 | Correct | 1 ms | 560 KB | Output is correct |
9 | Correct | 2 ms | 560 KB | Output is correct |
10 | Correct | 2 ms | 560 KB | Output is correct |
11 | Correct | 295 ms | 4588 KB | Output is correct |
12 | Correct | 296 ms | 4588 KB | Output is correct |
13 | Correct | 351 ms | 4588 KB | Output is correct |
14 | Correct | 297 ms | 4588 KB | Output is correct |
15 | Correct | 371 ms | 4588 KB | Output is correct |
16 | Correct | 321 ms | 4588 KB | Output is correct |
17 | Correct | 326 ms | 4588 KB | Output is correct |
18 | Correct | 223 ms | 5532 KB | Output is correct |
19 | Correct | 252 ms | 5532 KB | Output is correct |
20 | Correct | 289 ms | 5532 KB | Output is correct |
21 | Correct | 321 ms | 5532 KB | Output is correct |
22 | Correct | 329 ms | 5532 KB | Output is correct |
23 | Correct | 400 ms | 5532 KB | Output is correct |
24 | Correct | 379 ms | 5532 KB | Output is correct |
25 | Correct | 354 ms | 5664 KB | Output is correct |
26 | Correct | 388 ms | 5664 KB | Output is correct |
27 | Correct | 431 ms | 5664 KB | Output is correct |
28 | Correct | 245 ms | 6684 KB | Output is correct |
29 | Correct | 309 ms | 6684 KB | Output is correct |
30 | Correct | 330 ms | 6684 KB | Output is correct |
31 | Correct | 392 ms | 6684 KB | Output is correct |
32 | Correct | 395 ms | 6684 KB | Output is correct |
33 | Correct | 355 ms | 6684 KB | Output is correct |
34 | Correct | 419 ms | 6684 KB | Output is correct |
35 | Correct | 421 ms | 6684 KB | Output is correct |
36 | Correct | 239 ms | 6684 KB | Output is correct |
37 | Correct | 334 ms | 6684 KB | Output is correct |
38 | Correct | 346 ms | 6684 KB | Output is correct |
39 | Correct | 418 ms | 6684 KB | Output is correct |
40 | Correct | 397 ms | 6684 KB | Output is correct |
41 | Correct | 67 ms | 14236 KB | Output is correct |
42 | Correct | 71 ms | 14236 KB | Output is correct |
43 | Correct | 76 ms | 14364 KB | Output is correct |
44 | Correct | 76 ms | 14364 KB | Output is correct |
45 | Correct | 63 ms | 14364 KB | Output is correct |
46 | Correct | 79 ms | 14364 KB | Output is correct |
47 | Correct | 77 ms | 14364 KB | Output is correct |
48 | Correct | 53 ms | 14364 KB | Output is correct |
49 | Correct | 62 ms | 14364 KB | Output is correct |
50 | Correct | 66 ms | 14364 KB | Output is correct |
51 | Correct | 76 ms | 14364 KB | Output is correct |
52 | Correct | 77 ms | 14364 KB | Output is correct |
53 | Correct | 67 ms | 14364 KB | Output is correct |
54 | Correct | 77 ms | 14364 KB | Output is correct |
55 | Correct | 84 ms | 14364 KB | Output is correct |
56 | Correct | 51 ms | 14364 KB | Output is correct |
57 | Correct | 63 ms | 14364 KB | Output is correct |
58 | Correct | 67 ms | 14364 KB | Output is correct |
59 | Correct | 68 ms | 14364 KB | Output is correct |
60 | Correct | 71 ms | 14364 KB | Output is correct |
61 | Correct | 72 ms | 14364 KB | Output is correct |
62 | Correct | 101 ms | 14364 KB | Output is correct |
63 | Correct | 85 ms | 14364 KB | Output is correct |
64 | Correct | 54 ms | 14364 KB | Output is correct |
65 | Correct | 72 ms | 14364 KB | Output is correct |
66 | Correct | 85 ms | 14364 KB | Output is correct |
67 | Correct | 84 ms | 14364 KB | Output is correct |
68 | Correct | 75 ms | 14364 KB | Output is correct |
69 | Correct | 73 ms | 14364 KB | Output is correct |
70 | Correct | 75 ms | 14364 KB | Output is correct |
71 | Correct | 607 ms | 18812 KB | Output is correct |
72 | Correct | 617 ms | 19064 KB | Output is correct |
73 | Correct | 715 ms | 19064 KB | Output is correct |
74 | Correct | 886 ms | 19064 KB | Output is correct |
75 | Correct | 563 ms | 19780 KB | Output is correct |
76 | Correct | 1012 ms | 19780 KB | Output is correct |
77 | Correct | 881 ms | 19780 KB | Output is correct |
78 | Correct | 370 ms | 21820 KB | Output is correct |
79 | Correct | 527 ms | 21820 KB | Output is correct |
80 | Correct | 585 ms | 21820 KB | Output is correct |
81 | Correct | 737 ms | 21820 KB | Output is correct |
82 | Correct | 836 ms | 21820 KB | Output is correct |
83 | Correct | 532 ms | 21820 KB | Output is correct |
84 | Correct | 832 ms | 21820 KB | Output is correct |
85 | Correct | 923 ms | 21820 KB | Output is correct |
86 | Correct | 473 ms | 21820 KB | Output is correct |
87 | Correct | 554 ms | 21820 KB | Output is correct |
88 | Correct | 576 ms | 21820 KB | Output is correct |
89 | Correct | 679 ms | 21820 KB | Output is correct |
90 | Correct | 685 ms | 21820 KB | Output is correct |
91 | Correct | 534 ms | 21820 KB | Output is correct |
92 | Correct | 928 ms | 21820 KB | Output is correct |
93 | Correct | 931 ms | 21820 KB | Output is correct |
94 | Correct | 347 ms | 21820 KB | Output is correct |
95 | Correct | 798 ms | 21820 KB | Output is correct |
96 | Correct | 787 ms | 21820 KB | Output is correct |
97 | Correct | 839 ms | 21820 KB | Output is correct |
98 | Correct | 811 ms | 21820 KB | Output is correct |
99 | Correct | 742 ms | 21820 KB | Output is correct |
100 | Correct | 792 ms | 21820 KB | Output is correct |