# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41941 | 2018-02-22T06:17:30 Z | aome | Snake Escaping (JOI18_snake_escaping) | C++14 | 1603 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1 << 20; const int M = 3000005; int n, q; int to3[1 << 14]; int mask2[2][N]; // 0 check and, 1 check or int mask3[N]; int res[N]; int pw3[13], f[M], g[M]; char a[N]; void prepare() { for (int i = 0; i < (1 << 14); ++i) { for (int j = 13; j >= 0; --j) { to3[i] *= 3; if (i >> j & 1) to3[i]++; } } pw3[0] = 1; for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1]; for (int i = 0; i < M; ++i) { int cur = i; g[i] = -1; for (int j = 0; j < 14; ++j) { if (cur % 3 == 2) g[i] = j; cur /= 3; } } } void calc() { for (int i = 0; i < M; ++i) { if (g[i] != -1) { f[i] += f[i - 2 * pw3[g[i]]]; f[i] += f[i - 1 * pw3[g[i]]]; } } } int main() { scanf("%d %d %s", &n, &q, &a); for (int i = 0; i < q; ++i) { char s[20]; scanf("%s", &s); for (int j = max(0, n - 6); j < n; ++j) { // first 7 bits mask2[0][i] <<= 1, mask2[1][i] <<= 1; if (s[j] == '1') mask2[0][i]++; if (s[j] == '?' || s[j] == '1') mask2[1][i]++; } for (int j = 0; j < max(0, n - 6); ++j) { // last 13 bits mask3[i] *= 3; if (s[j] == '1') mask3[i]++; if (s[j] == '?') mask3[i] += 2; } } prepare(); for (int i = 0; i < 64; ++i) { // first 7 bits memset(f, 0, sizeof f); for (int j = 0; j < (1 << max(0, n - 6)); ++j) { f[to3[j]] += a[j << 6 | i] - '0'; } calc(); for (int j = 0; j < q; ++j) { if ((i & mask2[0][j]) == mask2[0][j] && (i | mask2[1][j]) == mask2[1][j]) res[j] += f[mask3[j]]; } } for (int i = 0; i < q; ++i) printf("%d\n", res[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 701 ms | 23928 KB | Output is correct |
2 | Correct | 676 ms | 24032 KB | Output is correct |
3 | Correct | 663 ms | 24120 KB | Output is correct |
4 | Correct | 720 ms | 24240 KB | Output is correct |
5 | Correct | 693 ms | 24240 KB | Output is correct |
6 | Correct | 664 ms | 24240 KB | Output is correct |
7 | Correct | 690 ms | 24240 KB | Output is correct |
8 | Correct | 692 ms | 24248 KB | Output is correct |
9 | Correct | 686 ms | 24300 KB | Output is correct |
10 | Correct | 677 ms | 24300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 701 ms | 23928 KB | Output is correct |
2 | Correct | 676 ms | 24032 KB | Output is correct |
3 | Correct | 663 ms | 24120 KB | Output is correct |
4 | Correct | 720 ms | 24240 KB | Output is correct |
5 | Correct | 693 ms | 24240 KB | Output is correct |
6 | Correct | 664 ms | 24240 KB | Output is correct |
7 | Correct | 690 ms | 24240 KB | Output is correct |
8 | Correct | 692 ms | 24248 KB | Output is correct |
9 | Correct | 686 ms | 24300 KB | Output is correct |
10 | Correct | 677 ms | 24300 KB | Output is correct |
11 | Correct | 1212 ms | 54564 KB | Output is correct |
12 | Correct | 1210 ms | 64988 KB | Output is correct |
13 | Correct | 1464 ms | 65536 KB | Output is correct |
14 | Correct | 1379 ms | 65536 KB | Output is correct |
15 | Correct | 1519 ms | 65536 KB | Output is correct |
16 | Correct | 1395 ms | 65536 KB | Output is correct |
17 | Correct | 1362 ms | 65536 KB | Output is correct |
18 | Correct | 1062 ms | 65536 KB | Output is correct |
19 | Correct | 1212 ms | 65536 KB | Output is correct |
20 | Correct | 1252 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 701 ms | 23928 KB | Output is correct |
2 | Correct | 676 ms | 24032 KB | Output is correct |
3 | Correct | 663 ms | 24120 KB | Output is correct |
4 | Correct | 720 ms | 24240 KB | Output is correct |
5 | Correct | 693 ms | 24240 KB | Output is correct |
6 | Correct | 664 ms | 24240 KB | Output is correct |
7 | Correct | 690 ms | 24240 KB | Output is correct |
8 | Correct | 692 ms | 24248 KB | Output is correct |
9 | Correct | 686 ms | 24300 KB | Output is correct |
10 | Correct | 677 ms | 24300 KB | Output is correct |
11 | Correct | 1212 ms | 54564 KB | Output is correct |
12 | Correct | 1210 ms | 64988 KB | Output is correct |
13 | Correct | 1464 ms | 65536 KB | Output is correct |
14 | Correct | 1379 ms | 65536 KB | Output is correct |
15 | Correct | 1519 ms | 65536 KB | Output is correct |
16 | Correct | 1395 ms | 65536 KB | Output is correct |
17 | Correct | 1362 ms | 65536 KB | Output is correct |
18 | Correct | 1062 ms | 65536 KB | Output is correct |
19 | Correct | 1212 ms | 65536 KB | Output is correct |
20 | Correct | 1252 ms | 65536 KB | Output is correct |
21 | Correct | 1270 ms | 65536 KB | Output is correct |
22 | Correct | 1267 ms | 65536 KB | Output is correct |
23 | Correct | 1453 ms | 65536 KB | Output is correct |
24 | Correct | 1602 ms | 65536 KB | Output is correct |
25 | Correct | 1603 ms | 65536 KB | Output is correct |
26 | Correct | 1478 ms | 65536 KB | Output is correct |
27 | Correct | 1461 ms | 65536 KB | Output is correct |
28 | Correct | 1155 ms | 65536 KB | Output is correct |
29 | Correct | 1338 ms | 65536 KB | Output is correct |
30 | Correct | 1311 ms | 65536 KB | Output is correct |
31 | Correct | 1515 ms | 65536 KB | Output is correct |
32 | Correct | 1417 ms | 65536 KB | Output is correct |
33 | Correct | 1283 ms | 65536 KB | Output is correct |
34 | Correct | 1400 ms | 65536 KB | Output is correct |
35 | Correct | 1452 ms | 65536 KB | Output is correct |
36 | Correct | 991 ms | 65536 KB | Output is correct |
37 | Correct | 1203 ms | 65536 KB | Output is correct |
38 | Correct | 1329 ms | 65536 KB | Output is correct |
39 | Correct | 1333 ms | 65536 KB | Output is correct |
40 | Correct | 1393 ms | 65536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 701 ms | 23928 KB | Output is correct |
2 | Correct | 676 ms | 24032 KB | Output is correct |
3 | Correct | 663 ms | 24120 KB | Output is correct |
4 | Correct | 720 ms | 24240 KB | Output is correct |
5 | Correct | 693 ms | 24240 KB | Output is correct |
6 | Correct | 664 ms | 24240 KB | Output is correct |
7 | Correct | 690 ms | 24240 KB | Output is correct |
8 | Correct | 692 ms | 24248 KB | Output is correct |
9 | Correct | 686 ms | 24300 KB | Output is correct |
10 | Correct | 677 ms | 24300 KB | Output is correct |
11 | Incorrect | 755 ms | 65536 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 701 ms | 23928 KB | Output is correct |
2 | Correct | 676 ms | 24032 KB | Output is correct |
3 | Correct | 663 ms | 24120 KB | Output is correct |
4 | Correct | 720 ms | 24240 KB | Output is correct |
5 | Correct | 693 ms | 24240 KB | Output is correct |
6 | Correct | 664 ms | 24240 KB | Output is correct |
7 | Correct | 690 ms | 24240 KB | Output is correct |
8 | Correct | 692 ms | 24248 KB | Output is correct |
9 | Correct | 686 ms | 24300 KB | Output is correct |
10 | Correct | 677 ms | 24300 KB | Output is correct |
11 | Correct | 1212 ms | 54564 KB | Output is correct |
12 | Correct | 1210 ms | 64988 KB | Output is correct |
13 | Correct | 1464 ms | 65536 KB | Output is correct |
14 | Correct | 1379 ms | 65536 KB | Output is correct |
15 | Correct | 1519 ms | 65536 KB | Output is correct |
16 | Correct | 1395 ms | 65536 KB | Output is correct |
17 | Correct | 1362 ms | 65536 KB | Output is correct |
18 | Correct | 1062 ms | 65536 KB | Output is correct |
19 | Correct | 1212 ms | 65536 KB | Output is correct |
20 | Correct | 1252 ms | 65536 KB | Output is correct |
21 | Correct | 1270 ms | 65536 KB | Output is correct |
22 | Correct | 1267 ms | 65536 KB | Output is correct |
23 | Correct | 1453 ms | 65536 KB | Output is correct |
24 | Correct | 1602 ms | 65536 KB | Output is correct |
25 | Correct | 1603 ms | 65536 KB | Output is correct |
26 | Correct | 1478 ms | 65536 KB | Output is correct |
27 | Correct | 1461 ms | 65536 KB | Output is correct |
28 | Correct | 1155 ms | 65536 KB | Output is correct |
29 | Correct | 1338 ms | 65536 KB | Output is correct |
30 | Correct | 1311 ms | 65536 KB | Output is correct |
31 | Correct | 1515 ms | 65536 KB | Output is correct |
32 | Correct | 1417 ms | 65536 KB | Output is correct |
33 | Correct | 1283 ms | 65536 KB | Output is correct |
34 | Correct | 1400 ms | 65536 KB | Output is correct |
35 | Correct | 1452 ms | 65536 KB | Output is correct |
36 | Correct | 991 ms | 65536 KB | Output is correct |
37 | Correct | 1203 ms | 65536 KB | Output is correct |
38 | Correct | 1329 ms | 65536 KB | Output is correct |
39 | Correct | 1333 ms | 65536 KB | Output is correct |
40 | Correct | 1393 ms | 65536 KB | Output is correct |
41 | Incorrect | 755 ms | 65536 KB | Output isn't correct |
42 | Halted | 0 ms | 0 KB | - |