답안 #523317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523317	2022-02-07T12:39:30 Z	sidon	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1954 ms	35192 KB

snake_escaping

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #523317

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0