# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
41938 | 2018-02-22T06:16:05 Z | aome | Snake Escaping (JOI18_snake_escaping) | C++14 | 1197 ms | 65536 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1 << 20; const int M = 1594323; 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 13048 KB | Output is correct |
2 | Correct | 371 ms | 13152 KB | Output is correct |
3 | Correct | 372 ms | 13152 KB | Output is correct |
4 | Correct | 373 ms | 13156 KB | Output is correct |
5 | Correct | 393 ms | 13184 KB | Output is correct |
6 | Correct | 378 ms | 13184 KB | Output is correct |
7 | Correct | 382 ms | 13224 KB | Output is correct |
8 | Correct | 371 ms | 13224 KB | Output is correct |
9 | Correct | 378 ms | 13224 KB | Output is correct |
10 | Correct | 370 ms | 13300 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 13048 KB | Output is correct |
2 | Correct | 371 ms | 13152 KB | Output is correct |
3 | Correct | 372 ms | 13152 KB | Output is correct |
4 | Correct | 373 ms | 13156 KB | Output is correct |
5 | Correct | 393 ms | 13184 KB | Output is correct |
6 | Correct | 378 ms | 13184 KB | Output is correct |
7 | Correct | 382 ms | 13224 KB | Output is correct |
8 | Correct | 371 ms | 13224 KB | Output is correct |
9 | Correct | 378 ms | 13224 KB | Output is correct |
10 | Correct | 370 ms | 13300 KB | Output is correct |
11 | Correct | 881 ms | 43628 KB | Output is correct |
12 | Correct | 891 ms | 54256 KB | Output is correct |
13 | Correct | 1061 ms | 64248 KB | Output is correct |
14 | Correct | 1014 ms | 65536 KB | Output is correct |
15 | Correct | 1144 ms | 65536 KB | Output is correct |
16 | Correct | 1040 ms | 65536 KB | Output is correct |
17 | Correct | 1047 ms | 65536 KB | Output is correct |
18 | Correct | 752 ms | 65536 KB | Output is correct |
19 | Correct | 868 ms | 65536 KB | Output is correct |
20 | Correct | 894 ms | 65536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 13048 KB | Output is correct |
2 | Correct | 371 ms | 13152 KB | Output is correct |
3 | Correct | 372 ms | 13152 KB | Output is correct |
4 | Correct | 373 ms | 13156 KB | Output is correct |
5 | Correct | 393 ms | 13184 KB | Output is correct |
6 | Correct | 378 ms | 13184 KB | Output is correct |
7 | Correct | 382 ms | 13224 KB | Output is correct |
8 | Correct | 371 ms | 13224 KB | Output is correct |
9 | Correct | 378 ms | 13224 KB | Output is correct |
10 | Correct | 370 ms | 13300 KB | Output is correct |
11 | Correct | 881 ms | 43628 KB | Output is correct |
12 | Correct | 891 ms | 54256 KB | Output is correct |
13 | Correct | 1061 ms | 64248 KB | Output is correct |
14 | Correct | 1014 ms | 65536 KB | Output is correct |
15 | Correct | 1144 ms | 65536 KB | Output is correct |
16 | Correct | 1040 ms | 65536 KB | Output is correct |
17 | Correct | 1047 ms | 65536 KB | Output is correct |
18 | Correct | 752 ms | 65536 KB | Output is correct |
19 | Correct | 868 ms | 65536 KB | Output is correct |
20 | Correct | 894 ms | 65536 KB | Output is correct |
21 | Correct | 924 ms | 65536 KB | Output is correct |
22 | Correct | 939 ms | 65536 KB | Output is correct |
23 | Correct | 1097 ms | 65536 KB | Output is correct |
24 | Correct | 1049 ms | 65536 KB | Output is correct |
25 | Correct | 1197 ms | 65536 KB | Output is correct |
26 | Correct | 1108 ms | 65536 KB | Output is correct |
27 | Correct | 1087 ms | 65536 KB | Output is correct |
28 | Correct | 817 ms | 65536 KB | Output is correct |
29 | Correct | 924 ms | 65536 KB | Output is correct |
30 | Correct | 923 ms | 65536 KB | Output is correct |
31 | Correct | 1132 ms | 65536 KB | Output is correct |
32 | Correct | 1077 ms | 65536 KB | Output is correct |
33 | Correct | 927 ms | 65536 KB | Output is correct |
34 | Correct | 1084 ms | 65536 KB | Output is correct |
35 | Correct | 1064 ms | 65536 KB | Output is correct |
36 | Correct | 655 ms | 65536 KB | Output is correct |
37 | Correct | 894 ms | 65536 KB | Output is correct |
38 | Correct | 981 ms | 65536 KB | Output is correct |
39 | Correct | 955 ms | 65536 KB | Output is correct |
40 | Correct | 1000 ms | 65536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 13048 KB | Output is correct |
2 | Correct | 371 ms | 13152 KB | Output is correct |
3 | Correct | 372 ms | 13152 KB | Output is correct |
4 | Correct | 373 ms | 13156 KB | Output is correct |
5 | Correct | 393 ms | 13184 KB | Output is correct |
6 | Correct | 378 ms | 13184 KB | Output is correct |
7 | Correct | 382 ms | 13224 KB | Output is correct |
8 | Correct | 371 ms | 13224 KB | Output is correct |
9 | Correct | 378 ms | 13224 KB | Output is correct |
10 | Correct | 370 ms | 13300 KB | Output is correct |
11 | Incorrect | 416 ms | 65536 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 375 ms | 13048 KB | Output is correct |
2 | Correct | 371 ms | 13152 KB | Output is correct |
3 | Correct | 372 ms | 13152 KB | Output is correct |
4 | Correct | 373 ms | 13156 KB | Output is correct |
5 | Correct | 393 ms | 13184 KB | Output is correct |
6 | Correct | 378 ms | 13184 KB | Output is correct |
7 | Correct | 382 ms | 13224 KB | Output is correct |
8 | Correct | 371 ms | 13224 KB | Output is correct |
9 | Correct | 378 ms | 13224 KB | Output is correct |
10 | Correct | 370 ms | 13300 KB | Output is correct |
11 | Correct | 881 ms | 43628 KB | Output is correct |
12 | Correct | 891 ms | 54256 KB | Output is correct |
13 | Correct | 1061 ms | 64248 KB | Output is correct |
14 | Correct | 1014 ms | 65536 KB | Output is correct |
15 | Correct | 1144 ms | 65536 KB | Output is correct |
16 | Correct | 1040 ms | 65536 KB | Output is correct |
17 | Correct | 1047 ms | 65536 KB | Output is correct |
18 | Correct | 752 ms | 65536 KB | Output is correct |
19 | Correct | 868 ms | 65536 KB | Output is correct |
20 | Correct | 894 ms | 65536 KB | Output is correct |
21 | Correct | 924 ms | 65536 KB | Output is correct |
22 | Correct | 939 ms | 65536 KB | Output is correct |
23 | Correct | 1097 ms | 65536 KB | Output is correct |
24 | Correct | 1049 ms | 65536 KB | Output is correct |
25 | Correct | 1197 ms | 65536 KB | Output is correct |
26 | Correct | 1108 ms | 65536 KB | Output is correct |
27 | Correct | 1087 ms | 65536 KB | Output is correct |
28 | Correct | 817 ms | 65536 KB | Output is correct |
29 | Correct | 924 ms | 65536 KB | Output is correct |
30 | Correct | 923 ms | 65536 KB | Output is correct |
31 | Correct | 1132 ms | 65536 KB | Output is correct |
32 | Correct | 1077 ms | 65536 KB | Output is correct |
33 | Correct | 927 ms | 65536 KB | Output is correct |
34 | Correct | 1084 ms | 65536 KB | Output is correct |
35 | Correct | 1064 ms | 65536 KB | Output is correct |
36 | Correct | 655 ms | 65536 KB | Output is correct |
37 | Correct | 894 ms | 65536 KB | Output is correct |
38 | Correct | 981 ms | 65536 KB | Output is correct |
39 | Correct | 955 ms | 65536 KB | Output is correct |
40 | Correct | 1000 ms | 65536 KB | Output is correct |
41 | Incorrect | 416 ms | 65536 KB | Output isn't correct |
42 | Halted | 0 ms | 0 KB | - |