oj.uz

Submission #523317

# Submission time Handle Problem Language Result Execution time Memory
523317 2022-02-07T12:39:30 Z sidon Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 1954 ms 35192 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) {
			int diff = x[i] ^ s;
			if((diff | y[i]) == diff)
				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 1044 ms 7628 KB Output is correct
2 Correct 1010 ms 7620 KB Output is correct
3 Correct 1024 ms 7604 KB Output is correct
4 Correct 1030 ms 7620 KB Output is correct
5 Correct 1054 ms 7604 KB Output is correct
6 Correct 1022 ms 7628 KB Output is correct
7 Correct 1006 ms 7628 KB Output is correct
8 Correct 1060 ms 7628 KB Output is correct
9 Correct 994 ms 7616 KB Output is correct
10 Correct 992 ms 7604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 7628 KB Output is correct
2 Correct 1010 ms 7620 KB Output is correct
3 Correct 1024 ms 7604 KB Output is correct
4 Correct 1030 ms 7620 KB Output is correct
5 Correct 1054 ms 7604 KB Output is correct
6 Correct 1022 ms 7628 KB Output is correct
7 Correct 1006 ms 7628 KB Output is correct
8 Correct 1060 ms 7628 KB Output is correct
9 Correct 994 ms 7616 KB Output is correct
10 Correct 992 ms 7604 KB Output is correct
11 Correct 1365 ms 19388 KB Output is correct
12 Correct 1362 ms 29816 KB Output is correct
13 Correct 1382 ms 29000 KB Output is correct
14 Correct 1410 ms 29100 KB Output is correct
15 Correct 1390 ms 30136 KB Output is correct
16 Correct 1380 ms 29232 KB Output is correct
17 Correct 1376 ms 29232 KB Output is correct
18 Correct 1356 ms 31180 KB Output is correct
19 Correct 1378 ms 28076 KB Output is correct
20 Correct 1366 ms 29744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 7628 KB Output is correct
2 Correct 1010 ms 7620 KB Output is correct
3 Correct 1024 ms 7604 KB Output is correct
4 Correct 1030 ms 7620 KB Output is correct
5 Correct 1054 ms 7604 KB Output is correct
6 Correct 1022 ms 7628 KB Output is correct
7 Correct 1006 ms 7628 KB Output is correct
8 Correct 1060 ms 7628 KB Output is correct
9 Correct 994 ms 7616 KB Output is correct
10 Correct 992 ms 7604 KB Output is correct
11 Correct 1365 ms 19388 KB Output is correct
12 Correct 1362 ms 29816 KB Output is correct
13 Correct 1382 ms 29000 KB Output is correct
14 Correct 1410 ms 29100 KB Output is correct
15 Correct 1390 ms 30136 KB Output is correct
16 Correct 1380 ms 29232 KB Output is correct
17 Correct 1376 ms 29232 KB Output is correct
18 Correct 1356 ms 31180 KB Output is correct
19 Correct 1378 ms 28076 KB Output is correct
20 Correct 1366 ms 29744 KB Output is correct
21 Correct 1365 ms 33200 KB Output is correct
22 Correct 1395 ms 33220 KB Output is correct
23 Correct 1589 ms 32300 KB Output is correct
24 Correct 1583 ms 32164 KB Output is correct
25 Correct 1495 ms 34124 KB Output is correct
26 Correct 1644 ms 32660 KB Output is correct
27 Correct 1821 ms 32576 KB Output is correct
28 Correct 1377 ms 35192 KB Output is correct
29 Correct 1371 ms 31136 KB Output is correct
30 Correct 1385 ms 33340 KB Output is correct
31 Correct 1580 ms 33136 KB Output is correct
32 Correct 1657 ms 33252 KB Output is correct
33 Correct 1465 ms 32028 KB Output is correct
34 Correct 1743 ms 32072 KB Output is correct
35 Correct 1954 ms 32604 KB Output is correct
36 Correct 1364 ms 31116 KB Output is correct
37 Correct 1373 ms 33204 KB Output is correct
38 Correct 1378 ms 31044 KB Output is correct
39 Correct 1543 ms 32196 KB Output is correct
40 Correct 1584 ms 32028 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 7628 KB Output is correct
2 Correct 1010 ms 7620 KB Output is correct
3 Correct 1024 ms 7604 KB Output is correct
4 Correct 1030 ms 7620 KB Output is correct
5 Correct 1054 ms 7604 KB Output is correct
6 Correct 1022 ms 7628 KB Output is correct
7 Correct 1006 ms 7628 KB Output is correct
8 Correct 1060 ms 7628 KB Output is correct
9 Correct 994 ms 7616 KB Output is correct
10 Correct 992 ms 7604 KB Output is correct
11 Incorrect 1026 ms 8960 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 7628 KB Output is correct
2 Correct 1010 ms 7620 KB Output is correct
3 Correct 1024 ms 7604 KB Output is correct
4 Correct 1030 ms 7620 KB Output is correct
5 Correct 1054 ms 7604 KB Output is correct
6 Correct 1022 ms 7628 KB Output is correct
7 Correct 1006 ms 7628 KB Output is correct
8 Correct 1060 ms 7628 KB Output is correct
9 Correct 994 ms 7616 KB Output is correct
10 Correct 992 ms 7604 KB Output is correct
11 Correct 1365 ms 19388 KB Output is correct
12 Correct 1362 ms 29816 KB Output is correct
13 Correct 1382 ms 29000 KB Output is correct
14 Correct 1410 ms 29100 KB Output is correct
15 Correct 1390 ms 30136 KB Output is correct
16 Correct 1380 ms 29232 KB Output is correct
17 Correct 1376 ms 29232 KB Output is correct
18 Correct 1356 ms 31180 KB Output is correct
19 Correct 1378 ms 28076 KB Output is correct
20 Correct 1366 ms 29744 KB Output is correct
21 Correct 1365 ms 33200 KB Output is correct
22 Correct 1395 ms 33220 KB Output is correct
23 Correct 1589 ms 32300 KB Output is correct
24 Correct 1583 ms 32164 KB Output is correct
25 Correct 1495 ms 34124 KB Output is correct
26 Correct 1644 ms 32660 KB Output is correct
27 Correct 1821 ms 32576 KB Output is correct
28 Correct 1377 ms 35192 KB Output is correct
29 Correct 1371 ms 31136 KB Output is correct
30 Correct 1385 ms 33340 KB Output is correct
31 Correct 1580 ms 33136 KB Output is correct
32 Correct 1657 ms 33252 KB Output is correct
33 Correct 1465 ms 32028 KB Output is correct
34 Correct 1743 ms 32072 KB Output is correct
35 Correct 1954 ms 32604 KB Output is correct
36 Correct 1364 ms 31116 KB Output is correct
37 Correct 1373 ms 33204 KB Output is correct
38 Correct 1378 ms 31044 KB Output is correct
39 Correct 1543 ms 32196 KB Output is correct
40 Correct 1584 ms 32028 KB Output is correct
41 Incorrect 1026 ms 8960 KB Output isn't correct
42 Halted 0 ms 0 KB -