# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
135189 | 2019-07-23T19:07:27 Z | duality | Snake Escaping (JOI18_snake_escaping) | C++11 | 2000 ms | 23892 KB |
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back typedef long long int LLI; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") int H = 9; char S[(1 << 20)+1],T[21]; struct query { int m1,m2,i; }; query queries[1000000]; int pow3[21]; int ans[1000000]; int num[1594323]; int sum[1594323]; int main() { int i,j; int L,Q; scanf("%d %d %s",&L,&Q,S); H = min(H,L); for (i = 0; i < Q; i++) { scanf("%s",T),queries[i].i = i; reverse(T,T+H),reverse(T+H,T+L); for (j = 0; j < H; j++) { if (T[j] == '0') queries[i].m1 |= (1 << (2*j)); else if (T[j] == '1') queries[i].m1 |= (1 << (2*j+1)); else queries[i].m1 |= (1 << (2*j)) | (1 << (2*j+1)); } int p = 1; for (j = H; j < L; j++) { if (T[j] == '1') queries[i].m2 += p; else if (T[j] == '?') queries[i].m2 += 2*p; p *= 3; } } int k; pow3[0] = 1; for (i = 1; i <= L; i++) pow3[i] = pow3[i-1]*3; for (i = 0; i < pow3[L-H]; i++) { int n = i; for (j = 0; j < L-H; j++) { if ((n % 3) == 2) num[i] |= (1 << j); n /= 3; } } for (i = 0; i < (1 << H); i++) { for (j = 0; j < (1 << (L-H)); j++) { int c = 0; for (k = 0; k < L-H; k++) { if (j & (1 << k)) c += pow3[k]; } sum[c] = S[j+i*(1 << (L-H))]-'0'; } for (j = 0; j < L-H; j++) { for (k = 0; k < pow3[L-H]; k++) { if (num[k] & (1 << j)) sum[k] = sum[k-pow3[j]]+sum[k-2*pow3[j]]; } } int m = 0; for (j = 0; j < H; j++) { if (i & (1 << j)) m |= (1 << (2*j+1)); else m |= (1 << (2*j)); } for (j = 0; j < Q; j++) { if ((queries[j].m1 & m) == m) ans[queries[j].i] += sum[queries[j].m2]; } } for (i = 0; i < Q; i++) printf("%d\n",ans[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 4 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 4 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 1145 ms | 20016 KB | Output is correct |
12 | Correct | 1405 ms | 19832 KB | Output is correct |
13 | Correct | 976 ms | 20916 KB | Output is correct |
14 | Correct | 994 ms | 20984 KB | Output is correct |
15 | Correct | 1599 ms | 22076 KB | Output is correct |
16 | Correct | 1114 ms | 21244 KB | Output is correct |
17 | Correct | 1212 ms | 21220 KB | Output is correct |
18 | Correct | 1891 ms | 23084 KB | Output is correct |
19 | Correct | 815 ms | 20216 KB | Output is correct |
20 | Correct | 1506 ms | 21664 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 4 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 1145 ms | 20016 KB | Output is correct |
12 | Correct | 1405 ms | 19832 KB | Output is correct |
13 | Correct | 976 ms | 20916 KB | Output is correct |
14 | Correct | 994 ms | 20984 KB | Output is correct |
15 | Correct | 1599 ms | 22076 KB | Output is correct |
16 | Correct | 1114 ms | 21244 KB | Output is correct |
17 | Correct | 1212 ms | 21220 KB | Output is correct |
18 | Correct | 1891 ms | 23084 KB | Output is correct |
19 | Correct | 815 ms | 20216 KB | Output is correct |
20 | Correct | 1506 ms | 21664 KB | Output is correct |
21 | Correct | 1444 ms | 21844 KB | Output is correct |
22 | Correct | 1453 ms | 22040 KB | Output is correct |
23 | Correct | 1068 ms | 21272 KB | Output is correct |
24 | Correct | 1114 ms | 21008 KB | Output is correct |
25 | Correct | 1724 ms | 22904 KB | Output is correct |
26 | Correct | 1255 ms | 21624 KB | Output is correct |
27 | Correct | 1210 ms | 21604 KB | Output is correct |
28 | Correct | 1933 ms | 23892 KB | Output is correct |
29 | Correct | 877 ms | 20100 KB | Output is correct |
30 | Correct | 1604 ms | 22204 KB | Output is correct |
31 | Correct | 1323 ms | 22068 KB | Output is correct |
32 | Correct | 1222 ms | 21980 KB | Output is correct |
33 | Correct | 931 ms | 20580 KB | Output is correct |
34 | Correct | 1070 ms | 20848 KB | Output is correct |
35 | Correct | 1180 ms | 21088 KB | Output is correct |
36 | Correct | 717 ms | 19548 KB | Output is correct |
37 | Correct | 1164 ms | 21492 KB | Output is correct |
38 | Correct | 896 ms | 19320 KB | Output is correct |
39 | Correct | 1164 ms | 20340 KB | Output is correct |
40 | Correct | 1204 ms | 20020 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 4 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 1279 ms | 3844 KB | Output is correct |
12 | Correct | 1288 ms | 3852 KB | Output is correct |
13 | Correct | 1282 ms | 3724 KB | Output is correct |
14 | Correct | 1292 ms | 3760 KB | Output is correct |
15 | Correct | 1329 ms | 3848 KB | Output is correct |
16 | Correct | 1301 ms | 3720 KB | Output is correct |
17 | Correct | 1285 ms | 3756 KB | Output is correct |
18 | Correct | 1309 ms | 3980 KB | Output is correct |
19 | Correct | 1272 ms | 3576 KB | Output is correct |
20 | Correct | 1298 ms | 3844 KB | Output is correct |
21 | Correct | 1298 ms | 3960 KB | Output is correct |
22 | Correct | 1280 ms | 3704 KB | Output is correct |
23 | Correct | 1257 ms | 3752 KB | Output is correct |
24 | Correct | 1269 ms | 3756 KB | Output is correct |
25 | Correct | 1296 ms | 3728 KB | Output is correct |
26 | Correct | 1266 ms | 3676 KB | Output is correct |
27 | Correct | 1281 ms | 3888 KB | Output is correct |
28 | Correct | 1257 ms | 3664 KB | Output is correct |
29 | Correct | 1273 ms | 3716 KB | Output is correct |
30 | Correct | 1269 ms | 3832 KB | Output is correct |
31 | Correct | 1257 ms | 3728 KB | Output is correct |
32 | Correct | 1280 ms | 3728 KB | Output is correct |
33 | Correct | 1295 ms | 3804 KB | Output is correct |
34 | Correct | 1249 ms | 3704 KB | Output is correct |
35 | Correct | 1299 ms | 3832 KB | Output is correct |
36 | Correct | 1297 ms | 3720 KB | Output is correct |
37 | Correct | 1306 ms | 3728 KB | Output is correct |
38 | Correct | 1301 ms | 3832 KB | Output is correct |
39 | Correct | 1304 ms | 3804 KB | Output is correct |
40 | Correct | 1296 ms | 3716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 3 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 3 ms | 376 KB | Output is correct |
6 | Correct | 3 ms | 376 KB | Output is correct |
7 | Correct | 3 ms | 376 KB | Output is correct |
8 | Correct | 4 ms | 376 KB | Output is correct |
9 | Correct | 3 ms | 376 KB | Output is correct |
10 | Correct | 3 ms | 376 KB | Output is correct |
11 | Correct | 1145 ms | 20016 KB | Output is correct |
12 | Correct | 1405 ms | 19832 KB | Output is correct |
13 | Correct | 976 ms | 20916 KB | Output is correct |
14 | Correct | 994 ms | 20984 KB | Output is correct |
15 | Correct | 1599 ms | 22076 KB | Output is correct |
16 | Correct | 1114 ms | 21244 KB | Output is correct |
17 | Correct | 1212 ms | 21220 KB | Output is correct |
18 | Correct | 1891 ms | 23084 KB | Output is correct |
19 | Correct | 815 ms | 20216 KB | Output is correct |
20 | Correct | 1506 ms | 21664 KB | Output is correct |
21 | Correct | 1444 ms | 21844 KB | Output is correct |
22 | Correct | 1453 ms | 22040 KB | Output is correct |
23 | Correct | 1068 ms | 21272 KB | Output is correct |
24 | Correct | 1114 ms | 21008 KB | Output is correct |
25 | Correct | 1724 ms | 22904 KB | Output is correct |
26 | Correct | 1255 ms | 21624 KB | Output is correct |
27 | Correct | 1210 ms | 21604 KB | Output is correct |
28 | Correct | 1933 ms | 23892 KB | Output is correct |
29 | Correct | 877 ms | 20100 KB | Output is correct |
30 | Correct | 1604 ms | 22204 KB | Output is correct |
31 | Correct | 1323 ms | 22068 KB | Output is correct |
32 | Correct | 1222 ms | 21980 KB | Output is correct |
33 | Correct | 931 ms | 20580 KB | Output is correct |
34 | Correct | 1070 ms | 20848 KB | Output is correct |
35 | Correct | 1180 ms | 21088 KB | Output is correct |
36 | Correct | 717 ms | 19548 KB | Output is correct |
37 | Correct | 1164 ms | 21492 KB | Output is correct |
38 | Correct | 896 ms | 19320 KB | Output is correct |
39 | Correct | 1164 ms | 20340 KB | Output is correct |
40 | Correct | 1204 ms | 20020 KB | Output is correct |
41 | Correct | 1279 ms | 3844 KB | Output is correct |
42 | Correct | 1288 ms | 3852 KB | Output is correct |
43 | Correct | 1282 ms | 3724 KB | Output is correct |
44 | Correct | 1292 ms | 3760 KB | Output is correct |
45 | Correct | 1329 ms | 3848 KB | Output is correct |
46 | Correct | 1301 ms | 3720 KB | Output is correct |
47 | Correct | 1285 ms | 3756 KB | Output is correct |
48 | Correct | 1309 ms | 3980 KB | Output is correct |
49 | Correct | 1272 ms | 3576 KB | Output is correct |
50 | Correct | 1298 ms | 3844 KB | Output is correct |
51 | Correct | 1298 ms | 3960 KB | Output is correct |
52 | Correct | 1280 ms | 3704 KB | Output is correct |
53 | Correct | 1257 ms | 3752 KB | Output is correct |
54 | Correct | 1269 ms | 3756 KB | Output is correct |
55 | Correct | 1296 ms | 3728 KB | Output is correct |
56 | Correct | 1266 ms | 3676 KB | Output is correct |
57 | Correct | 1281 ms | 3888 KB | Output is correct |
58 | Correct | 1257 ms | 3664 KB | Output is correct |
59 | Correct | 1273 ms | 3716 KB | Output is correct |
60 | Correct | 1269 ms | 3832 KB | Output is correct |
61 | Correct | 1257 ms | 3728 KB | Output is correct |
62 | Correct | 1280 ms | 3728 KB | Output is correct |
63 | Correct | 1295 ms | 3804 KB | Output is correct |
64 | Correct | 1249 ms | 3704 KB | Output is correct |
65 | Correct | 1299 ms | 3832 KB | Output is correct |
66 | Correct | 1297 ms | 3720 KB | Output is correct |
67 | Correct | 1306 ms | 3728 KB | Output is correct |
68 | Correct | 1301 ms | 3832 KB | Output is correct |
69 | Correct | 1304 ms | 3804 KB | Output is correct |
70 | Correct | 1296 ms | 3716 KB | Output is correct |
71 | Execution timed out | 2054 ms | 18612 KB | Time limit exceeded |
72 | Halted | 0 ms | 0 KB | - |