답안 #379381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379381	2021-03-18T05:27:30 Z	cheissmart	Snake Escaping (JOI18_snake_escaping)	C++14	75 / 100	2000 ms	40344 KB

snake_escaping

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 20;

int a[1 << 20], sub[1 << N], sup[1 << N];

signed main()
{
	IO_OP;
	
	int l, q;
	cin >> l >> q;
	for(int i = 0; i < (1 << l); i++) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	memcpy(sub, a, sizeof(a[0]) * (1 << l));
	memcpy(sup, a, sizeof(a[0]) * (1 << l));
	for(int j = 0; j < l; j++) {
		for(int i = 0; i < (1 << l); i++)
			if(i >> j & 1)
				sub[i] += sub[i ^ (1 << j)];
	}
	for(int j = 0; j < l; j++) {
		for(int i = 0; i < (1 << l); i++)
			if(i >> j & 1)
				sup[i ^ (1 << j)] += sup[i];
	}
	while(q--) {
		string s;
		cin >> s;
		reverse(ALL(s));
		vi one, zero, any;
		for(int i = 0; i < l; i++) {
			if(s[i] == '1') one.PB(i);
			else if(s[i] == '0') zero.PB(i);
			else any.PB(i);
		}
		int m1 = 0, m2 = 0;
		for(int i = 0; i < l; i++) {
			if(s[i] == '?') m2 |= 1 << i;
			else m1 |= (s[i] - '0') << i;
		}
		if(int(one.size()) <= 6) {
			int ans = 0;
			for(int m = m1; ; m = (m - 1) & m1) {
				int sign = (__builtin_popcount(m ^ m1) % 2 ? -1 : 1);
				ans += sign * sub[m | m2];
				if(m == 0) break;
			}
			cout << ans << '\n';			
		} else if(int(zero.size()) <= 6) {
			int ans = 0;
			int all = ((1 << l) - 1) ^ m2;
			m1 ^= all;
			for(int m = m1; ; m = (m - 1) & m1) {
				int mm = all ^ m;
				int sign = (__builtin_popcount(m ^ m1) % 2 ? -1 : 1);
				ans += sign * sup[mm];
				if(m == 0) break;
			}
			cout << ans << '\n';
		} else {
			int ans = 0;
			for(int m = m2; ; m = (m - 1) & m2) {
				ans += a[m1 | m];
				if(m == 0) break;
			}
			cout << ans << '\n';
		}
	}

}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Correct	741 ms	15392 KB	Output is correct
12	Correct	573 ms	14956 KB	Output is correct
13	Correct	638 ms	14040 KB	Output is correct
14	Correct	648 ms	14316 KB	Output is correct
15	Correct	596 ms	15212 KB	Output is correct
16	Correct	724 ms	14372 KB	Output is correct
17	Correct	725 ms	14372 KB	Output is correct
18	Correct	396 ms	16236 KB	Output is correct
19	Correct	697 ms	13220 KB	Output is correct
20	Correct	690 ms	14880 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Correct	741 ms	15392 KB	Output is correct
12	Correct	573 ms	14956 KB	Output is correct
13	Correct	638 ms	14040 KB	Output is correct
14	Correct	648 ms	14316 KB	Output is correct
15	Correct	596 ms	15212 KB	Output is correct
16	Correct	724 ms	14372 KB	Output is correct
17	Correct	725 ms	14372 KB	Output is correct
18	Correct	396 ms	16236 KB	Output is correct
19	Correct	697 ms	13220 KB	Output is correct
20	Correct	690 ms	14880 KB	Output is correct
21	Correct	935 ms	18288 KB	Output is correct
22	Correct	666 ms	18540 KB	Output is correct
23	Correct	794 ms	17388 KB	Output is correct
24	Correct	800 ms	17292 KB	Output is correct
25	Correct	711 ms	19300 KB	Output is correct
26	Correct	876 ms	17728 KB	Output is correct
27	Correct	875 ms	17772 KB	Output is correct
28	Correct	418 ms	20316 KB	Output is correct
29	Correct	876 ms	16192 KB	Output is correct
30	Correct	786 ms	18412 KB	Output is correct
31	Correct	871 ms	18268 KB	Output is correct
32	Correct	837 ms	18284 KB	Output is correct
33	Correct	787 ms	17176 KB	Output is correct
34	Correct	858 ms	17256 KB	Output is correct
35	Correct	917 ms	17664 KB	Output is correct
36	Correct	432 ms	16320 KB	Output is correct
37	Correct	658 ms	18512 KB	Output is correct
38	Correct	793 ms	16472 KB	Output is correct
39	Correct	1036 ms	17452 KB	Output is correct
40	Correct	896 ms	17344 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Correct	118 ms	14924 KB	Output is correct
12	Correct	116 ms	15212 KB	Output is correct
13	Correct	129 ms	14904 KB	Output is correct
14	Correct	155 ms	15084 KB	Output is correct
15	Correct	120 ms	14956 KB	Output is correct
16	Correct	162 ms	14956 KB	Output is correct
17	Correct	172 ms	14976 KB	Output is correct
18	Correct	92 ms	15084 KB	Output is correct
19	Correct	109 ms	14956 KB	Output is correct
20	Correct	139 ms	15004 KB	Output is correct
21	Correct	139 ms	15124 KB	Output is correct
22	Correct	144 ms	14956 KB	Output is correct
23	Correct	120 ms	14956 KB	Output is correct
24	Correct	167 ms	14956 KB	Output is correct
25	Correct	158 ms	14956 KB	Output is correct
26	Correct	94 ms	14812 KB	Output is correct
27	Correct	119 ms	15084 KB	Output is correct
28	Correct	111 ms	14828 KB	Output is correct
29	Correct	135 ms	14956 KB	Output is correct
30	Correct	126 ms	14956 KB	Output is correct
31	Correct	119 ms	14828 KB	Output is correct
32	Correct	171 ms	14956 KB	Output is correct
33	Correct	162 ms	14904 KB	Output is correct
34	Correct	96 ms	14876 KB	Output is correct
35	Correct	160 ms	14956 KB	Output is correct
36	Correct	143 ms	15084 KB	Output is correct
37	Correct	146 ms	14956 KB	Output is correct
38	Correct	154 ms	14956 KB	Output is correct
39	Correct	155 ms	14956 KB	Output is correct
40	Correct	141 ms	15084 KB	Output is correct

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	2 ms	364 KB	Output is correct
11	Correct	741 ms	15392 KB	Output is correct
12	Correct	573 ms	14956 KB	Output is correct
13	Correct	638 ms	14040 KB	Output is correct
14	Correct	648 ms	14316 KB	Output is correct
15	Correct	596 ms	15212 KB	Output is correct
16	Correct	724 ms	14372 KB	Output is correct
17	Correct	725 ms	14372 KB	Output is correct
18	Correct	396 ms	16236 KB	Output is correct
19	Correct	697 ms	13220 KB	Output is correct
20	Correct	690 ms	14880 KB	Output is correct
21	Correct	935 ms	18288 KB	Output is correct
22	Correct	666 ms	18540 KB	Output is correct
23	Correct	794 ms	17388 KB	Output is correct
24	Correct	800 ms	17292 KB	Output is correct
25	Correct	711 ms	19300 KB	Output is correct
26	Correct	876 ms	17728 KB	Output is correct
27	Correct	875 ms	17772 KB	Output is correct
28	Correct	418 ms	20316 KB	Output is correct
29	Correct	876 ms	16192 KB	Output is correct
30	Correct	786 ms	18412 KB	Output is correct
31	Correct	871 ms	18268 KB	Output is correct
32	Correct	837 ms	18284 KB	Output is correct
33	Correct	787 ms	17176 KB	Output is correct
34	Correct	858 ms	17256 KB	Output is correct
35	Correct	917 ms	17664 KB	Output is correct
36	Correct	432 ms	16320 KB	Output is correct
37	Correct	658 ms	18512 KB	Output is correct
38	Correct	793 ms	16472 KB	Output is correct
39	Correct	1036 ms	17452 KB	Output is correct
40	Correct	896 ms	17344 KB	Output is correct
41	Correct	118 ms	14924 KB	Output is correct
42	Correct	116 ms	15212 KB	Output is correct
43	Correct	129 ms	14904 KB	Output is correct
44	Correct	155 ms	15084 KB	Output is correct
45	Correct	120 ms	14956 KB	Output is correct
46	Correct	162 ms	14956 KB	Output is correct
47	Correct	172 ms	14976 KB	Output is correct
48	Correct	92 ms	15084 KB	Output is correct
49	Correct	109 ms	14956 KB	Output is correct
50	Correct	139 ms	15004 KB	Output is correct
51	Correct	139 ms	15124 KB	Output is correct
52	Correct	144 ms	14956 KB	Output is correct
53	Correct	120 ms	14956 KB	Output is correct
54	Correct	167 ms	14956 KB	Output is correct
55	Correct	158 ms	14956 KB	Output is correct
56	Correct	94 ms	14812 KB	Output is correct
57	Correct	119 ms	15084 KB	Output is correct
58	Correct	111 ms	14828 KB	Output is correct
59	Correct	135 ms	14956 KB	Output is correct
60	Correct	126 ms	14956 KB	Output is correct
61	Correct	119 ms	14828 KB	Output is correct
62	Correct	171 ms	14956 KB	Output is correct
63	Correct	162 ms	14904 KB	Output is correct
64	Correct	96 ms	14876 KB	Output is correct
65	Correct	160 ms	14956 KB	Output is correct
66	Correct	143 ms	15084 KB	Output is correct
67	Correct	146 ms	14956 KB	Output is correct
68	Correct	154 ms	14956 KB	Output is correct
69	Correct	155 ms	14956 KB	Output is correct
70	Correct	141 ms	15084 KB	Output is correct
71	Correct	1040 ms	39256 KB	Output is correct
72	Correct	1080 ms	39376 KB	Output is correct
73	Correct	1420 ms	37996 KB	Output is correct
74	Correct	1799 ms	38528 KB	Output is correct
75	Correct	1186 ms	40344 KB	Output is correct
76	Execution timed out	2072 ms	37984 KB	Time limit exceeded
77	Halted	0 ms	0 KB	-

답안 #379381

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