답안 #523326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523326	2022-02-07T13:00:24 Z	sidon	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2000 ms	38768 KB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
 
const int B = 14, 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]))
				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	1580 ms	20104 KB	Output is correct
2	Correct	1519 ms	20152 KB	Output is correct
3	Correct	1576 ms	20172 KB	Output is correct
4	Correct	1499 ms	20104 KB	Output is correct
5	Correct	1528 ms	20108 KB	Output is correct
6	Correct	1579 ms	20104 KB	Output is correct
7	Correct	1552 ms	20104 KB	Output is correct
8	Correct	1575 ms	20112 KB	Output is correct
9	Correct	1490 ms	20044 KB	Output is correct
10	Correct	1468 ms	20104 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1580 ms	20104 KB	Output is correct
2	Correct	1519 ms	20152 KB	Output is correct
3	Correct	1576 ms	20172 KB	Output is correct
4	Correct	1499 ms	20104 KB	Output is correct
5	Correct	1528 ms	20108 KB	Output is correct
6	Correct	1579 ms	20104 KB	Output is correct
7	Correct	1552 ms	20104 KB	Output is correct
8	Correct	1575 ms	20112 KB	Output is correct
9	Correct	1490 ms	20044 KB	Output is correct
10	Correct	1468 ms	20104 KB	Output is correct
11	Correct	1718 ms	35676 KB	Output is correct
12	Correct	1726 ms	35352 KB	Output is correct
13	Correct	1708 ms	34628 KB	Output is correct
14	Correct	1724 ms	34744 KB	Output is correct
15	Correct	1710 ms	35716 KB	Output is correct
16	Correct	1735 ms	34960 KB	Output is correct
17	Correct	1697 ms	34840 KB	Output is correct
18	Correct	1728 ms	36756 KB	Output is correct
19	Correct	1719 ms	33728 KB	Output is correct
20	Correct	1702 ms	35448 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1580 ms	20104 KB	Output is correct
2	Correct	1519 ms	20152 KB	Output is correct
3	Correct	1576 ms	20172 KB	Output is correct
4	Correct	1499 ms	20104 KB	Output is correct
5	Correct	1528 ms	20108 KB	Output is correct
6	Correct	1579 ms	20104 KB	Output is correct
7	Correct	1552 ms	20104 KB	Output is correct
8	Correct	1575 ms	20112 KB	Output is correct
9	Correct	1490 ms	20044 KB	Output is correct
10	Correct	1468 ms	20104 KB	Output is correct
11	Correct	1718 ms	35676 KB	Output is correct
12	Correct	1726 ms	35352 KB	Output is correct
13	Correct	1708 ms	34628 KB	Output is correct
14	Correct	1724 ms	34744 KB	Output is correct
15	Correct	1710 ms	35716 KB	Output is correct
16	Correct	1735 ms	34960 KB	Output is correct
17	Correct	1697 ms	34840 KB	Output is correct
18	Correct	1728 ms	36756 KB	Output is correct
19	Correct	1719 ms	33728 KB	Output is correct
20	Correct	1702 ms	35448 KB	Output is correct
21	Correct	1718 ms	35820 KB	Output is correct
22	Correct	1764 ms	35908 KB	Output is correct
23	Correct	1738 ms	34976 KB	Output is correct
24	Correct	1730 ms	34740 KB	Output is correct
25	Correct	1739 ms	36792 KB	Output is correct
26	Correct	1716 ms	35336 KB	Output is correct
27	Correct	1730 ms	35248 KB	Output is correct
28	Correct	1702 ms	37796 KB	Output is correct
29	Correct	1733 ms	33804 KB	Output is correct
30	Correct	1710 ms	35964 KB	Output is correct
31	Correct	1692 ms	35760 KB	Output is correct
32	Correct	1703 ms	35780 KB	Output is correct
33	Correct	1738 ms	34612 KB	Output is correct
34	Correct	1717 ms	34812 KB	Output is correct
35	Correct	1743 ms	35248 KB	Output is correct
36	Correct	1686 ms	33712 KB	Output is correct
37	Correct	1732 ms	35764 KB	Output is correct
38	Correct	1710 ms	33784 KB	Output is correct
39	Correct	1708 ms	34900 KB	Output is correct
40	Correct	1698 ms	34736 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1580 ms	20104 KB	Output is correct
2	Correct	1519 ms	20152 KB	Output is correct
3	Correct	1576 ms	20172 KB	Output is correct
4	Correct	1499 ms	20104 KB	Output is correct
5	Correct	1528 ms	20108 KB	Output is correct
6	Correct	1579 ms	20104 KB	Output is correct
7	Correct	1552 ms	20104 KB	Output is correct
8	Correct	1575 ms	20112 KB	Output is correct
9	Correct	1490 ms	20044 KB	Output is correct
10	Correct	1468 ms	20104 KB	Output is correct
11	Correct	1521 ms	22212 KB	Output is correct
12	Correct	1491 ms	22276 KB	Output is correct
13	Correct	1521 ms	22208 KB	Output is correct
14	Correct	1506 ms	22372 KB	Output is correct
15	Correct	1525 ms	22340 KB	Output is correct
16	Correct	1538 ms	22244 KB	Output is correct
17	Correct	1524 ms	22212 KB	Output is correct
18	Correct	1575 ms	22280 KB	Output is correct
19	Correct	1493 ms	22084 KB	Output is correct
20	Correct	1508 ms	22344 KB	Output is correct
21	Correct	1639 ms	22216 KB	Output is correct
22	Correct	1613 ms	22472 KB	Output is correct
23	Correct	1619 ms	22468 KB	Output is correct
24	Correct	1554 ms	22468 KB	Output is correct
25	Correct	1573 ms	22980 KB	Output is correct
26	Correct	1547 ms	22884 KB	Output is correct
27	Correct	1599 ms	22884 KB	Output is correct
28	Correct	1579 ms	22852 KB	Output is correct
29	Correct	1543 ms	22952 KB	Output is correct
30	Correct	1643 ms	22984 KB	Output is correct
31	Correct	1622 ms	22984 KB	Output is correct
32	Correct	1601 ms	22980 KB	Output is correct
33	Correct	1562 ms	23060 KB	Output is correct
34	Correct	1611 ms	22752 KB	Output is correct
35	Correct	1668 ms	22984 KB	Output is correct
36	Correct	1580 ms	22984 KB	Output is correct
37	Correct	1552 ms	23012 KB	Output is correct
38	Correct	1613 ms	22984 KB	Output is correct
39	Correct	1500 ms	22980 KB	Output is correct
40	Correct	1497 ms	22984 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1580 ms	20104 KB	Output is correct
2	Correct	1519 ms	20152 KB	Output is correct
3	Correct	1576 ms	20172 KB	Output is correct
4	Correct	1499 ms	20104 KB	Output is correct
5	Correct	1528 ms	20108 KB	Output is correct
6	Correct	1579 ms	20104 KB	Output is correct
7	Correct	1552 ms	20104 KB	Output is correct
8	Correct	1575 ms	20112 KB	Output is correct
9	Correct	1490 ms	20044 KB	Output is correct
10	Correct	1468 ms	20104 KB	Output is correct
11	Correct	1718 ms	35676 KB	Output is correct
12	Correct	1726 ms	35352 KB	Output is correct
13	Correct	1708 ms	34628 KB	Output is correct
14	Correct	1724 ms	34744 KB	Output is correct
15	Correct	1710 ms	35716 KB	Output is correct
16	Correct	1735 ms	34960 KB	Output is correct
17	Correct	1697 ms	34840 KB	Output is correct
18	Correct	1728 ms	36756 KB	Output is correct
19	Correct	1719 ms	33728 KB	Output is correct
20	Correct	1702 ms	35448 KB	Output is correct
21	Correct	1718 ms	35820 KB	Output is correct
22	Correct	1764 ms	35908 KB	Output is correct
23	Correct	1738 ms	34976 KB	Output is correct
24	Correct	1730 ms	34740 KB	Output is correct
25	Correct	1739 ms	36792 KB	Output is correct
26	Correct	1716 ms	35336 KB	Output is correct
27	Correct	1730 ms	35248 KB	Output is correct
28	Correct	1702 ms	37796 KB	Output is correct
29	Correct	1733 ms	33804 KB	Output is correct
30	Correct	1710 ms	35964 KB	Output is correct
31	Correct	1692 ms	35760 KB	Output is correct
32	Correct	1703 ms	35780 KB	Output is correct
33	Correct	1738 ms	34612 KB	Output is correct
34	Correct	1717 ms	34812 KB	Output is correct
35	Correct	1743 ms	35248 KB	Output is correct
36	Correct	1686 ms	33712 KB	Output is correct
37	Correct	1732 ms	35764 KB	Output is correct
38	Correct	1710 ms	33784 KB	Output is correct
39	Correct	1708 ms	34900 KB	Output is correct
40	Correct	1698 ms	34736 KB	Output is correct
41	Correct	1521 ms	22212 KB	Output is correct
42	Correct	1491 ms	22276 KB	Output is correct
43	Correct	1521 ms	22208 KB	Output is correct
44	Correct	1506 ms	22372 KB	Output is correct
45	Correct	1525 ms	22340 KB	Output is correct
46	Correct	1538 ms	22244 KB	Output is correct
47	Correct	1524 ms	22212 KB	Output is correct
48	Correct	1575 ms	22280 KB	Output is correct
49	Correct	1493 ms	22084 KB	Output is correct
50	Correct	1508 ms	22344 KB	Output is correct
51	Correct	1639 ms	22216 KB	Output is correct
52	Correct	1613 ms	22472 KB	Output is correct
53	Correct	1619 ms	22468 KB	Output is correct
54	Correct	1554 ms	22468 KB	Output is correct
55	Correct	1573 ms	22980 KB	Output is correct
56	Correct	1547 ms	22884 KB	Output is correct
57	Correct	1599 ms	22884 KB	Output is correct
58	Correct	1579 ms	22852 KB	Output is correct
59	Correct	1543 ms	22952 KB	Output is correct
60	Correct	1643 ms	22984 KB	Output is correct
61	Correct	1622 ms	22984 KB	Output is correct
62	Correct	1601 ms	22980 KB	Output is correct
63	Correct	1562 ms	23060 KB	Output is correct
64	Correct	1611 ms	22752 KB	Output is correct
65	Correct	1668 ms	22984 KB	Output is correct
66	Correct	1580 ms	22984 KB	Output is correct
67	Correct	1552 ms	23012 KB	Output is correct
68	Correct	1613 ms	22984 KB	Output is correct
69	Correct	1500 ms	22980 KB	Output is correct
70	Correct	1497 ms	22984 KB	Output is correct
71	Correct	1865 ms	38120 KB	Output is correct
72	Correct	1844 ms	35980 KB	Output is correct
73	Correct	1929 ms	36452 KB	Output is correct
74	Correct	1998 ms	36840 KB	Output is correct
75	Execution timed out	2058 ms	38768 KB	Time limit exceeded
76	Halted	0 ms	0 KB	-

답안 #523326

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 53.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
53.0 / 53.0

Subtask #5
0 / 25.0