Submission #547582

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547582	2022-04-11T03:06:41 Z	8e7	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1907 ms	39224 KB

snake_escaping

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1<<20
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int s0[maxn], s1[maxn];
int main() {
	io
	int n, q;
	cin >> n >> q;
	string s;	
	cin >> s;
	for (int i = 0;i < (1<<n);i++) s0[i] = s1[i] = s[i] - '0';	
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < (1<<n);j++) {
			if (j & (1<<i)) {
				s1[j] += s1[j - (1<<i)];
			} else {
				s0[j] += s0[j + (1<<i)];
			}
		}
	}	
	while (q--) {
		string se;
		cin >> se;
		reverse(se.begin(), se.end());
		int c[3] = {0, 0, 0};
		for (int i = 0;i < n;i++) {
			if (se[i] == '?') se[i] = '2';
			c[se[i] - '0']++;
		}
		int mi = min_element(c, c+3) - c;	
		//debug(mi);
		vector<int> pos;
		int p = 0;
		for (int i = 0;i < n;i++) {
			if (se[i] - '0' == mi) pos.push_back(i);
			else {
				if (se[i] - '0' == 2) p += (1<<i) * mi;
				else p += (1<<i) * (se[i] - '0');
			}
		}
		int siz = pos.size();
		int ans = 0;
		for (int i = 0;i < (1<<siz);i++) {
			int add = p;		
			for (int j = 0;j < siz;j++) {
				if (i & (1<<j)) add += 1<<pos[j];
			}
			if (mi == 2) ans += s[add] - '0'; 	
			else {
				int k = __builtin_popcount(i);
				if (mi == 1) {
					k = siz - k;
					ans += (k % 2 ? -1 : 1) * s1[add];
					//debug(add, (k % 2 ? -1 : 1) * s1[add]);
				} else {
					ans += (k % 2 ? -1 : 1) * s0[add];
					//debug(add, (k % 2 ? -1 : 1) * s0[add]);
				}
			}
		}
		cout << ans << "\n";
		//debug();
	}
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	1 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	1 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	248 ms	15060 KB	Output is correct
12	Correct	307 ms	14764 KB	Output is correct
13	Correct	353 ms	14028 KB	Output is correct
14	Correct	436 ms	14084 KB	Output is correct
15	Correct	349 ms	15152 KB	Output is correct
16	Correct	421 ms	14284 KB	Output is correct
17	Correct	409 ms	14284 KB	Output is correct
18	Correct	236 ms	16004 KB	Output is correct
19	Correct	211 ms	13012 KB	Output is correct
20	Correct	281 ms	14760 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	1 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	248 ms	15060 KB	Output is correct
12	Correct	307 ms	14764 KB	Output is correct
13	Correct	353 ms	14028 KB	Output is correct
14	Correct	436 ms	14084 KB	Output is correct
15	Correct	349 ms	15152 KB	Output is correct
16	Correct	421 ms	14284 KB	Output is correct
17	Correct	409 ms	14284 KB	Output is correct
18	Correct	236 ms	16004 KB	Output is correct
19	Correct	211 ms	13012 KB	Output is correct
20	Correct	281 ms	14760 KB	Output is correct
21	Correct	331 ms	18128 KB	Output is correct
22	Correct	366 ms	18200 KB	Output is correct
23	Correct	442 ms	17196 KB	Output is correct
24	Correct	573 ms	17292 KB	Output is correct
25	Correct	434 ms	19120 KB	Output is correct
26	Correct	540 ms	17612 KB	Output is correct
27	Correct	519 ms	17612 KB	Output is correct
28	Correct	285 ms	20068 KB	Output is correct
29	Correct	231 ms	16148 KB	Output is correct
30	Correct	361 ms	18252 KB	Output is correct
31	Correct	494 ms	18104 KB	Output is correct
32	Correct	581 ms	18068 KB	Output is correct
33	Correct	376 ms	16908 KB	Output is correct
34	Correct	565 ms	17216 KB	Output is correct
35	Correct	527 ms	17512 KB	Output is correct
36	Correct	235 ms	16228 KB	Output is correct
37	Correct	327 ms	18068 KB	Output is correct
38	Correct	234 ms	16144 KB	Output is correct
39	Correct	440 ms	17208 KB	Output is correct
40	Correct	542 ms	17108 KB	Output is correct

Subtask #4
53.0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	1 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	60 ms	12012 KB	Output is correct
12	Correct	53 ms	11944 KB	Output is correct
13	Correct	66 ms	11836 KB	Output is correct
14	Correct	134 ms	11920 KB	Output is correct
15	Correct	64 ms	11964 KB	Output is correct
16	Correct	98 ms	11904 KB	Output is correct
17	Correct	94 ms	11860 KB	Output is correct
18	Correct	49 ms	12048 KB	Output is correct
19	Correct	44 ms	11704 KB	Output is correct
20	Correct	53 ms	11944 KB	Output is correct
21	Correct	74 ms	11968 KB	Output is correct
22	Correct	110 ms	11840 KB	Output is correct
23	Correct	58 ms	11788 KB	Output is correct
24	Correct	118 ms	11860 KB	Output is correct
25	Correct	97 ms	11888 KB	Output is correct
26	Correct	43 ms	11768 KB	Output is correct
27	Correct	54 ms	11960 KB	Output is correct
28	Correct	42 ms	11756 KB	Output is correct
29	Correct	81 ms	11824 KB	Output is correct
30	Correct	91 ms	11848 KB	Output is correct
31	Correct	53 ms	11844 KB	Output is correct
32	Correct	107 ms	11832 KB	Output is correct
33	Correct	108 ms	11892 KB	Output is correct
34	Correct	42 ms	11708 KB	Output is correct
35	Correct	83 ms	11860 KB	Output is correct
36	Correct	85 ms	11836 KB	Output is correct
37	Correct	84 ms	11932 KB	Output is correct
38	Correct	81 ms	11888 KB	Output is correct
39	Correct	78 ms	11996 KB	Output is correct
40	Correct	83 ms	11928 KB	Output is correct

Subtask #5
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	1 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	248 ms	15060 KB	Output is correct
12	Correct	307 ms	14764 KB	Output is correct
13	Correct	353 ms	14028 KB	Output is correct
14	Correct	436 ms	14084 KB	Output is correct
15	Correct	349 ms	15152 KB	Output is correct
16	Correct	421 ms	14284 KB	Output is correct
17	Correct	409 ms	14284 KB	Output is correct
18	Correct	236 ms	16004 KB	Output is correct
19	Correct	211 ms	13012 KB	Output is correct
20	Correct	281 ms	14760 KB	Output is correct
21	Correct	331 ms	18128 KB	Output is correct
22	Correct	366 ms	18200 KB	Output is correct
23	Correct	442 ms	17196 KB	Output is correct
24	Correct	573 ms	17292 KB	Output is correct
25	Correct	434 ms	19120 KB	Output is correct
26	Correct	540 ms	17612 KB	Output is correct
27	Correct	519 ms	17612 KB	Output is correct
28	Correct	285 ms	20068 KB	Output is correct
29	Correct	231 ms	16148 KB	Output is correct
30	Correct	361 ms	18252 KB	Output is correct
31	Correct	494 ms	18104 KB	Output is correct
32	Correct	581 ms	18068 KB	Output is correct
33	Correct	376 ms	16908 KB	Output is correct
34	Correct	565 ms	17216 KB	Output is correct
35	Correct	527 ms	17512 KB	Output is correct
36	Correct	235 ms	16228 KB	Output is correct
37	Correct	327 ms	18068 KB	Output is correct
38	Correct	234 ms	16144 KB	Output is correct
39	Correct	440 ms	17208 KB	Output is correct
40	Correct	542 ms	17108 KB	Output is correct
41	Correct	60 ms	12012 KB	Output is correct
42	Correct	53 ms	11944 KB	Output is correct
43	Correct	66 ms	11836 KB	Output is correct
44	Correct	134 ms	11920 KB	Output is correct
45	Correct	64 ms	11964 KB	Output is correct
46	Correct	98 ms	11904 KB	Output is correct
47	Correct	94 ms	11860 KB	Output is correct
48	Correct	49 ms	12048 KB	Output is correct
49	Correct	44 ms	11704 KB	Output is correct
50	Correct	53 ms	11944 KB	Output is correct
51	Correct	74 ms	11968 KB	Output is correct
52	Correct	110 ms	11840 KB	Output is correct
53	Correct	58 ms	11788 KB	Output is correct
54	Correct	118 ms	11860 KB	Output is correct
55	Correct	97 ms	11888 KB	Output is correct
56	Correct	43 ms	11768 KB	Output is correct
57	Correct	54 ms	11960 KB	Output is correct
58	Correct	42 ms	11756 KB	Output is correct
59	Correct	81 ms	11824 KB	Output is correct
60	Correct	91 ms	11848 KB	Output is correct
61	Correct	53 ms	11844 KB	Output is correct
62	Correct	107 ms	11832 KB	Output is correct
63	Correct	108 ms	11892 KB	Output is correct
64	Correct	42 ms	11708 KB	Output is correct
65	Correct	83 ms	11860 KB	Output is correct
66	Correct	85 ms	11836 KB	Output is correct
67	Correct	84 ms	11932 KB	Output is correct
68	Correct	81 ms	11888 KB	Output is correct
69	Correct	78 ms	11996 KB	Output is correct
70	Correct	83 ms	11928 KB	Output is correct
71	Correct	575 ms	36248 KB	Output is correct
72	Correct	583 ms	36388 KB	Output is correct
73	Correct	907 ms	34860 KB	Output is correct
74	Correct	1907 ms	35404 KB	Output is correct
75	Correct	654 ms	37336 KB	Output is correct
76	Correct	1413 ms	35576 KB	Output is correct
77	Correct	1296 ms	35504 KB	Output is correct
78	Correct	408 ms	39224 KB	Output is correct
79	Correct	363 ms	33260 KB	Output is correct
80	Correct	547 ms	36392 KB	Output is correct
81	Correct	906 ms	36204 KB	Output is correct
82	Correct	1423 ms	35388 KB	Output is correct
83	Correct	624 ms	34364 KB	Output is correct
84	Correct	1601 ms	35292 KB	Output is correct
85	Correct	1322 ms	35504 KB	Output is correct
86	Correct	366 ms	33272 KB	Output is correct
87	Correct	557 ms	36204 KB	Output is correct
88	Correct	387 ms	33212 KB	Output is correct
89	Correct	806 ms	34872 KB	Output is correct
90	Correct	1232 ms	35352 KB	Output is correct
91	Correct	568 ms	34500 KB	Output is correct
92	Correct	1693 ms	35636 KB	Output is correct
93	Correct	1382 ms	35416 KB	Output is correct
94	Correct	342 ms	33152 KB	Output is correct
95	Correct	1087 ms	35304 KB	Output is correct
96	Correct	1060 ms	35368 KB	Output is correct
97	Correct	1069 ms	35304 KB	Output is correct
98	Correct	1125 ms	35336 KB	Output is correct
99	Correct	1076 ms	35452 KB	Output is correct
100	Correct	1061 ms	35380 KB	Output is correct

Submission #547582

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