oj.uz

Submission #523318

# Submission time Handle Problem Language Result Execution time Memory
523318 2022-02-07T12:49:03 Z sidon Snake Escaping (JOI18_snake_escaping) C++17
100 / 100
 1768 ms 47036 KB 
#include <bits/stdc++.h>
using namespace std;

const int B = 13, N = 1<<20, SZ = pow(3, B);

int Q, dp[SZ], ans[N], id[N];
string A, inp;
short x[N], y[N];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> Q >> Q >> A;
	A.resize(N, '0');

	for(int i = 0; i < Q; ++i) {
		cin >> inp;
		reverse(begin(inp), end(inp));
		inp.resize(20, '0');

		for(int k = 0, p = 1; k < B; ++k, p *= 3)
			id[i] += p * ((48 < inp[k]) + (62 < inp[k]));

		for(int k = 0; k < 20-B; ++k) {
			if(inp[k+B] == '?')	y[i] |= 1<<k;
			if(inp[k+B] == '1')	x[i] |= 1<<k;
		}
	}

	for(int s = 0; s < (1<<(20-B)); ++s) {
		memset(dp, 0, sizeof dp);

		for(int i = 0; i < (1<<B); ++i) {
			int j = 0;
			for(int k = 0, p = 1; k < B; ++k, p *= 3)
				if(i & (1<<k)) j += p;

			dp[j] += A[i | (s << B)] - '0';
		}

		for(int i = 1; i < SZ; ++i) {
			int j = -1, pw = 1;

			for(int k = 0, p = i; k < B; ++k, p /= 3, pw *= 3)
				if((p % 3) > 1) j = k, k = B;
			
			if(j >= 0)
				pw /= 3, dp[i] = dp[i - pw] + dp[i - 2 * pw];
		}

		for(int i = 0; i < Q; ++i)
			if(((x[i] ^ s) | y[i]) == y[i])
				ans[i] += dp[id[i]];
	}

	for(int i = 0; i < Q; ++i)
		cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 7624 KB Output is correct
2 Correct 1004 ms 7620 KB Output is correct
3 Correct 1020 ms 7644 KB Output is correct
4 Correct 994 ms 7748 KB Output is correct
5 Correct 996 ms 7744 KB Output is correct
6 Correct 995 ms 7628 KB Output is correct
7 Correct 1000 ms 7624 KB Output is correct
8 Correct 997 ms 7640 KB Output is correct
9 Correct 1010 ms 7628 KB Output is correct
10 Correct 1014 ms 7620 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 7624 KB Output is correct
2 Correct 1004 ms 7620 KB Output is correct
3 Correct 1020 ms 7644 KB Output is correct
4 Correct 994 ms 7748 KB Output is correct
5 Correct 996 ms 7744 KB Output is correct
6 Correct 995 ms 7628 KB Output is correct
7 Correct 1000 ms 7624 KB Output is correct
8 Correct 997 ms 7640 KB Output is correct
9 Correct 1010 ms 7628 KB Output is correct
10 Correct 1014 ms 7620 KB Output is correct
11 Correct 1291 ms 20532 KB Output is correct
12 Correct 1303 ms 20156 KB Output is correct
13 Correct 1307 ms 19388 KB Output is correct
14 Correct 1298 ms 19484 KB Output is correct
15 Correct 1315 ms 20656 KB Output is correct
16 Correct 1274 ms 19636 KB Output is correct
17 Correct 1307 ms 19640 KB Output is correct
18 Correct 1293 ms 21500 KB Output is correct
19 Correct 1278 ms 18468 KB Output is correct
20 Correct 1289 ms 20264 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 7624 KB Output is correct
2 Correct 1004 ms 7620 KB Output is correct
3 Correct 1020 ms 7644 KB Output is correct
4 Correct 994 ms 7748 KB Output is correct
5 Correct 996 ms 7744 KB Output is correct
6 Correct 995 ms 7628 KB Output is correct
7 Correct 1000 ms 7624 KB Output is correct
8 Correct 997 ms 7640 KB Output is correct
9 Correct 1010 ms 7628 KB Output is correct
10 Correct 1014 ms 7620 KB Output is correct
11 Correct 1291 ms 20532 KB Output is correct
12 Correct 1303 ms 20156 KB Output is correct
13 Correct 1307 ms 19388 KB Output is correct
14 Correct 1298 ms 19484 KB Output is correct
15 Correct 1315 ms 20656 KB Output is correct
16 Correct 1274 ms 19636 KB Output is correct
17 Correct 1307 ms 19640 KB Output is correct
18 Correct 1293 ms 21500 KB Output is correct
19 Correct 1278 ms 18468 KB Output is correct
20 Correct 1289 ms 20264 KB Output is correct
21 Correct 1285 ms 20608 KB Output is correct
22 Correct 1321 ms 20688 KB Output is correct
23 Correct 1291 ms 19836 KB Output is correct
24 Correct 1295 ms 19532 KB Output is correct
25 Correct 1297 ms 21572 KB Output is correct
26 Correct 1298 ms 20164 KB Output is correct
27 Correct 1295 ms 20060 KB Output is correct
28 Correct 1312 ms 22600 KB Output is correct
29 Correct 1282 ms 18380 KB Output is correct
30 Correct 1313 ms 20792 KB Output is correct
31 Correct 1289 ms 20424 KB Output is correct
32 Correct 1297 ms 20380 KB Output is correct
33 Correct 1303 ms 19396 KB Output is correct
34 Correct 1276 ms 19344 KB Output is correct
35 Correct 1301 ms 19660 KB Output is correct
36 Correct 1300 ms 18188 KB Output is correct
37 Correct 1308 ms 20092 KB Output is correct
38 Correct 1287 ms 18180 KB Output is correct
39 Correct 1293 ms 19240 KB Output is correct
40 Correct 1285 ms 18896 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 7624 KB Output is correct
2 Correct 1004 ms 7620 KB Output is correct
3 Correct 1020 ms 7644 KB Output is correct
4 Correct 994 ms 7748 KB Output is correct
5 Correct 996 ms 7744 KB Output is correct
6 Correct 995 ms 7628 KB Output is correct
7 Correct 1000 ms 7624 KB Output is correct
8 Correct 997 ms 7640 KB Output is correct
9 Correct 1010 ms 7628 KB Output is correct
10 Correct 1014 ms 7620 KB Output is correct
11 Correct 1031 ms 9280 KB Output is correct
12 Correct 1024 ms 9500 KB Output is correct
13 Correct 1042 ms 9572 KB Output is correct
14 Correct 1035 ms 9472 KB Output is correct
15 Correct 1051 ms 9600 KB Output is correct
16 Correct 1035 ms 9476 KB Output is correct
17 Correct 1028 ms 9564 KB Output is correct
18 Correct 1016 ms 9832 KB Output is correct
19 Correct 1018 ms 9244 KB Output is correct
20 Correct 1022 ms 9604 KB Output is correct
21 Correct 1016 ms 9512 KB Output is correct
22 Correct 1022 ms 9476 KB Output is correct
23 Correct 1025 ms 9460 KB Output is correct
24 Correct 1016 ms 9568 KB Output is correct
25 Correct 1020 ms 9472 KB Output is correct
26 Correct 1014 ms 9296 KB Output is correct
27 Correct 1031 ms 9376 KB Output is correct
28 Correct 1018 ms 9328 KB Output is correct
29 Correct 1016 ms 9468 KB Output is correct
30 Correct 1010 ms 9468 KB Output is correct
31 Correct 1016 ms 9512 KB Output is correct
32 Correct 1029 ms 9476 KB Output is correct
33 Correct 1014 ms 9540 KB Output is correct
34 Correct 1010 ms 9148 KB Output is correct
35 Correct 1018 ms 9476 KB Output is correct
36 Correct 1041 ms 9488 KB Output is correct
37 Correct 1024 ms 9496 KB Output is correct
38 Correct 1057 ms 9480 KB Output is correct
39 Correct 1057 ms 9580 KB Output is correct
40 Correct 1031 ms 9472 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 7624 KB Output is correct
2 Correct 1004 ms 7620 KB Output is correct
3 Correct 1020 ms 7644 KB Output is correct
4 Correct 994 ms 7748 KB Output is correct
5 Correct 996 ms 7744 KB Output is correct
6 Correct 995 ms 7628 KB Output is correct
7 Correct 1000 ms 7624 KB Output is correct
8 Correct 997 ms 7640 KB Output is correct
9 Correct 1010 ms 7628 KB Output is correct
10 Correct 1014 ms 7620 KB Output is correct
11 Correct 1291 ms 20532 KB Output is correct
12 Correct 1303 ms 20156 KB Output is correct
13 Correct 1307 ms 19388 KB Output is correct
14 Correct 1298 ms 19484 KB Output is correct
15 Correct 1315 ms 20656 KB Output is correct
16 Correct 1274 ms 19636 KB Output is correct
17 Correct 1307 ms 19640 KB Output is correct
18 Correct 1293 ms 21500 KB Output is correct
19 Correct 1278 ms 18468 KB Output is correct
20 Correct 1289 ms 20264 KB Output is correct
21 Correct 1285 ms 20608 KB Output is correct
22 Correct 1321 ms 20688 KB Output is correct
23 Correct 1291 ms 19836 KB Output is correct
24 Correct 1295 ms 19532 KB Output is correct
25 Correct 1297 ms 21572 KB Output is correct
26 Correct 1298 ms 20164 KB Output is correct
27 Correct 1295 ms 20060 KB Output is correct
28 Correct 1312 ms 22600 KB Output is correct
29 Correct 1282 ms 18380 KB Output is correct
30 Correct 1313 ms 20792 KB Output is correct
31 Correct 1289 ms 20424 KB Output is correct
32 Correct 1297 ms 20380 KB Output is correct
33 Correct 1303 ms 19396 KB Output is correct
34 Correct 1276 ms 19344 KB Output is correct
35 Correct 1301 ms 19660 KB Output is correct
36 Correct 1300 ms 18188 KB Output is correct
37 Correct 1308 ms 20092 KB Output is correct
38 Correct 1287 ms 18180 KB Output is correct
39 Correct 1293 ms 19240 KB Output is correct
40 Correct 1285 ms 18896 KB Output is correct
41 Correct 1031 ms 9280 KB Output is correct
42 Correct 1024 ms 9500 KB Output is correct
43 Correct 1042 ms 9572 KB Output is correct
44 Correct 1035 ms 9472 KB Output is correct
45 Correct 1051 ms 9600 KB Output is correct
46 Correct 1035 ms 9476 KB Output is correct
47 Correct 1028 ms 9564 KB Output is correct
48 Correct 1016 ms 9832 KB Output is correct
49 Correct 1018 ms 9244 KB Output is correct
50 Correct 1022 ms 9604 KB Output is correct
51 Correct 1016 ms 9512 KB Output is correct
52 Correct 1022 ms 9476 KB Output is correct
53 Correct 1025 ms 9460 KB Output is correct
54 Correct 1016 ms 9568 KB Output is correct
55 Correct 1020 ms 9472 KB Output is correct
56 Correct 1014 ms 9296 KB Output is correct
57 Correct 1031 ms 9376 KB Output is correct
58 Correct 1018 ms 9328 KB Output is correct
59 Correct 1016 ms 9468 KB Output is correct
60 Correct 1010 ms 9468 KB Output is correct
61 Correct 1016 ms 9512 KB Output is correct
62 Correct 1029 ms 9476 KB Output is correct
63 Correct 1014 ms 9540 KB Output is correct
64 Correct 1010 ms 9148 KB Output is correct
65 Correct 1018 ms 9476 KB Output is correct
66 Correct 1041 ms 9488 KB Output is correct
67 Correct 1024 ms 9496 KB Output is correct
68 Correct 1057 ms 9480 KB Output is correct
69 Correct 1057 ms 9580 KB Output is correct
70 Correct 1031 ms 9472 KB Output is correct
71 Correct 1563 ms 46092 KB Output is correct
72 Correct 1534 ms 44144 KB Output is correct
73 Correct 1546 ms 44560 KB Output is correct
74 Correct 1605 ms 45064 KB Output is correct
75 Correct 1768 ms 46980 KB Output is correct
76 Correct 1656 ms 45200 KB Output is correct
77 Correct 1707 ms 45164 KB Output is correct
78 Correct 1393 ms 47036 KB Output is correct
79 Correct 1423 ms 41196 KB Output is correct
80 Correct 1530 ms 46184 KB Output is correct
81 Correct 1713 ms 45976 KB Output is correct
82 Correct 1619 ms 44980 KB Output is correct
83 Correct 1441 ms 44348 KB Output is correct
84 Correct 1626 ms 45028 KB Output is correct
85 Correct 1658 ms 45076 KB Output is correct
86 Correct 1294 ms 41000 KB Output is correct
87 Correct 1533 ms 44040 KB Output is correct
88 Correct 1426 ms 41080 KB Output is correct
89 Correct 1540 ms 44564 KB Output is correct
90 Correct 1598 ms 44936 KB Output is correct
91 Correct 1437 ms 44040 KB Output is correct
92 Correct 1658 ms 45320 KB Output is correct
93 Correct 1644 ms 45136 KB Output is correct
94 Correct 1320 ms 39060 KB Output is correct
95 Correct 1651 ms 45188 KB Output is correct
96 Correct 1673 ms 45072 KB Output is correct
97 Correct 1660 ms 45144 KB Output is correct
98 Correct 1673 ms 44976 KB Output is correct
99 Correct 1632 ms 45044 KB Output is correct
100 Correct 1663 ms 45116 KB Output is correct