답안 #535670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535670	2022-03-10T21:44:48 Z	iliaM	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1657 ms	24648 KB

snake_escaping

#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = (1 << 20) + 10;

int a[N], f[N], g[N], h[N];
int n, m;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 0; i < (1 << n); ++i) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	
	int comp = (1 << n) - 1;
	for (int i = 0; i < (1 << n); ++i) {
		f[i] = g[i ^ comp] = a[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int mask = 0; mask < (1 << n); ++mask) {
			if ((mask >> i) & 1) {
				f[mask] += f[mask ^ (1 << i)];
				g[mask] += g[mask ^ (1 << i)];
			}
		}
	}
	for (int i = 0; i < (1 << n); ++i) {
		h[i] = g[i ^ comp];
	}
	
	while (m--) {
		string s;
		cin >> s;
		int cnt0 = 0, cnt1 = 0, num = 0, numm = 0;
		reverse(s.begin(), s.end());
		vector<int> idx[3];
		fill(idx, idx + 3, vector<int>());
		for (int i = 0; i < n; ++i) {
			cnt0 += s[i] == '0';
			cnt1 += s[i] == '1';
			if (s[i] == '1') {
				idx[1].push_back(i);
				num += (1 << i);
				numm += (1 << i);
			}
			if (s[i] == '?') {
				idx[2].push_back(i);
				numm += (1 << i);
			}
			if (s[i] == '0') {
				idx[0].push_back(i);
			}
		}

		int sum = 0;
		if (cnt1 <= 6) {
			for (int mask = 0; mask < (1 << cnt1); ++mask) {
				int num2 = numm;
				for (int i = 0; i < (int) idx[1].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[1][i];
				}
				sum += (__builtin_parity(mask) ? -1 : +1) * f[num2];
			}
		} else if (n - cnt0 - cnt1 <= 6) {
			int cnt = n - cnt0 - cnt1;
			for (int mask = 0; mask < (1 << cnt); ++mask) {
				int num2 = num;
				for (int i = 0; i < (int) idx[2].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[2][i];
				}
				sum += a[num2];
			}
		} else {
			for (int mask = 0; mask < (1 << cnt0); ++mask) {
				int num2 = num;
				for (int i = 0; i < (int) idx[0].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[0][i];
				}
				sum += (__builtin_parity(mask) ? -1 : +1) * h[num2];
			}
		}
		cout << sum << '\n';
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	656 ms	4300 KB	Output is correct
12	Correct	455 ms	4036 KB	Output is correct
13	Correct	548 ms	3268 KB	Output is correct
14	Correct	558 ms	3444 KB	Output is correct
15	Correct	493 ms	4336 KB	Output is correct
16	Correct	601 ms	3636 KB	Output is correct
17	Correct	624 ms	3444 KB	Output is correct
18	Correct	308 ms	5380 KB	Output is correct
19	Correct	602 ms	2336 KB	Output is correct
20	Correct	606 ms	4172 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	656 ms	4300 KB	Output is correct
12	Correct	455 ms	4036 KB	Output is correct
13	Correct	548 ms	3268 KB	Output is correct
14	Correct	558 ms	3444 KB	Output is correct
15	Correct	493 ms	4336 KB	Output is correct
16	Correct	601 ms	3636 KB	Output is correct
17	Correct	624 ms	3444 KB	Output is correct
18	Correct	308 ms	5380 KB	Output is correct
19	Correct	602 ms	2336 KB	Output is correct
20	Correct	606 ms	4172 KB	Output is correct
21	Correct	886 ms	4428 KB	Output is correct
22	Correct	521 ms	4588 KB	Output is correct
23	Correct	672 ms	3568 KB	Output is correct
24	Correct	704 ms	3628 KB	Output is correct
25	Correct	561 ms	5560 KB	Output is correct
26	Correct	729 ms	3912 KB	Output is correct
27	Correct	723 ms	3964 KB	Output is correct
28	Correct	329 ms	6556 KB	Output is correct
29	Correct	489 ms	2460 KB	Output is correct
30	Correct	712 ms	4552 KB	Output is correct
31	Correct	673 ms	4468 KB	Output is correct
32	Correct	723 ms	4452 KB	Output is correct
33	Correct	569 ms	3276 KB	Output is correct
34	Correct	722 ms	3508 KB	Output is correct
35	Correct	736 ms	3908 KB	Output is correct
36	Correct	336 ms	2368 KB	Output is correct
37	Correct	506 ms	4392 KB	Output is correct
38	Correct	621 ms	2420 KB	Output is correct
39	Correct	960 ms	3644 KB	Output is correct
40	Correct	743 ms	3380 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	81 ms	17012 KB	Output is correct
12	Correct	78 ms	16900 KB	Output is correct
13	Correct	114 ms	16856 KB	Output is correct
14	Correct	105 ms	16972 KB	Output is correct
15	Correct	76 ms	17012 KB	Output is correct
16	Correct	122 ms	16840 KB	Output is correct
17	Correct	108 ms	16876 KB	Output is correct
18	Correct	56 ms	17060 KB	Output is correct
19	Correct	74 ms	16788 KB	Output is correct
20	Correct	73 ms	16952 KB	Output is correct
21	Correct	86 ms	16860 KB	Output is correct
22	Correct	97 ms	16844 KB	Output is correct
23	Correct	82 ms	16852 KB	Output is correct
24	Correct	115 ms	16852 KB	Output is correct
25	Correct	108 ms	16908 KB	Output is correct
26	Correct	55 ms	16724 KB	Output is correct
27	Correct	72 ms	16864 KB	Output is correct
28	Correct	72 ms	16728 KB	Output is correct
29	Correct	87 ms	16856 KB	Output is correct
30	Correct	123 ms	16824 KB	Output is correct
31	Correct	74 ms	16844 KB	Output is correct
32	Correct	105 ms	16868 KB	Output is correct
33	Correct	119 ms	16856 KB	Output is correct
34	Correct	65 ms	16716 KB	Output is correct
35	Correct	112 ms	16844 KB	Output is correct
36	Correct	97 ms	16848 KB	Output is correct
37	Correct	96 ms	16896 KB	Output is correct
38	Correct	98 ms	16856 KB	Output is correct
39	Correct	98 ms	16892 KB	Output is correct
40	Correct	96 ms	16876 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	372 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	656 ms	4300 KB	Output is correct
12	Correct	455 ms	4036 KB	Output is correct
13	Correct	548 ms	3268 KB	Output is correct
14	Correct	558 ms	3444 KB	Output is correct
15	Correct	493 ms	4336 KB	Output is correct
16	Correct	601 ms	3636 KB	Output is correct
17	Correct	624 ms	3444 KB	Output is correct
18	Correct	308 ms	5380 KB	Output is correct
19	Correct	602 ms	2336 KB	Output is correct
20	Correct	606 ms	4172 KB	Output is correct
21	Correct	886 ms	4428 KB	Output is correct
22	Correct	521 ms	4588 KB	Output is correct
23	Correct	672 ms	3568 KB	Output is correct
24	Correct	704 ms	3628 KB	Output is correct
25	Correct	561 ms	5560 KB	Output is correct
26	Correct	729 ms	3912 KB	Output is correct
27	Correct	723 ms	3964 KB	Output is correct
28	Correct	329 ms	6556 KB	Output is correct
29	Correct	489 ms	2460 KB	Output is correct
30	Correct	712 ms	4552 KB	Output is correct
31	Correct	673 ms	4468 KB	Output is correct
32	Correct	723 ms	4452 KB	Output is correct
33	Correct	569 ms	3276 KB	Output is correct
34	Correct	722 ms	3508 KB	Output is correct
35	Correct	736 ms	3908 KB	Output is correct
36	Correct	336 ms	2368 KB	Output is correct
37	Correct	506 ms	4392 KB	Output is correct
38	Correct	621 ms	2420 KB	Output is correct
39	Correct	960 ms	3644 KB	Output is correct
40	Correct	743 ms	3380 KB	Output is correct
41	Correct	81 ms	17012 KB	Output is correct
42	Correct	78 ms	16900 KB	Output is correct
43	Correct	114 ms	16856 KB	Output is correct
44	Correct	105 ms	16972 KB	Output is correct
45	Correct	76 ms	17012 KB	Output is correct
46	Correct	122 ms	16840 KB	Output is correct
47	Correct	108 ms	16876 KB	Output is correct
48	Correct	56 ms	17060 KB	Output is correct
49	Correct	74 ms	16788 KB	Output is correct
50	Correct	73 ms	16952 KB	Output is correct
51	Correct	86 ms	16860 KB	Output is correct
52	Correct	97 ms	16844 KB	Output is correct
53	Correct	82 ms	16852 KB	Output is correct
54	Correct	115 ms	16852 KB	Output is correct
55	Correct	108 ms	16908 KB	Output is correct
56	Correct	55 ms	16724 KB	Output is correct
57	Correct	72 ms	16864 KB	Output is correct
58	Correct	72 ms	16728 KB	Output is correct
59	Correct	87 ms	16856 KB	Output is correct
60	Correct	123 ms	16824 KB	Output is correct
61	Correct	74 ms	16844 KB	Output is correct
62	Correct	105 ms	16868 KB	Output is correct
63	Correct	119 ms	16856 KB	Output is correct
64	Correct	65 ms	16716 KB	Output is correct
65	Correct	112 ms	16844 KB	Output is correct
66	Correct	97 ms	16848 KB	Output is correct
67	Correct	96 ms	16896 KB	Output is correct
68	Correct	98 ms	16856 KB	Output is correct
69	Correct	98 ms	16892 KB	Output is correct
70	Correct	96 ms	16876 KB	Output is correct
71	Correct	781 ms	21728 KB	Output is correct
72	Correct	731 ms	21848 KB	Output is correct
73	Correct	1043 ms	20552 KB	Output is correct
74	Correct	1387 ms	20748 KB	Output is correct
75	Correct	818 ms	22676 KB	Output is correct
76	Correct	1657 ms	21196 KB	Output is correct
77	Correct	1494 ms	20968 KB	Output is correct
78	Correct	488 ms	24648 KB	Output is correct
79	Correct	752 ms	18688 KB	Output is correct
80	Correct	791 ms	21832 KB	Output is correct
81	Correct	1067 ms	21860 KB	Output is correct
82	Correct	1345 ms	20684 KB	Output is correct
83	Correct	831 ms	19864 KB	Output is correct
84	Correct	1552 ms	20700 KB	Output is correct
85	Correct	1444 ms	20968 KB	Output is correct
86	Correct	429 ms	18740 KB	Output is correct
87	Correct	729 ms	21736 KB	Output is correct
88	Correct	775 ms	18864 KB	Output is correct
89	Correct	1121 ms	20300 KB	Output is correct
90	Correct	1203 ms	20800 KB	Output is correct
91	Correct	818 ms	20132 KB	Output is correct
92	Correct	1305 ms	21036 KB	Output is correct
93	Correct	1464 ms	21068 KB	Output is correct
94	Correct	467 ms	18656 KB	Output is correct
95	Correct	1313 ms	20812 KB	Output is correct
96	Correct	1227 ms	20808 KB	Output is correct
97	Correct	1271 ms	20816 KB	Output is correct
98	Correct	1237 ms	20896 KB	Output is correct
99	Correct	1218 ms	20812 KB	Output is correct
100	Correct	1247 ms	20836 KB	Output is correct

답안 #535670

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 25.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
25.0 / 25.0