답안 #391295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391295	2021-04-18T13:02:42 Z	sinamhdv	Snake Escaping (JOI18_snake_escaping)	C++11	100 / 100	1450 ms	39164 KB

snake_escaping

// JOI18_snake_escaping
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 22
#define BND 0

int n, q;
char s[1 << MAXN];
int sosub[1 << MAXN], sosup[1 << MAXN];

int32_t main(void)
{
	fast_io;
	cin >> n >> q >> s;
	FOR(i, 0, 1 << n) sosub[i] = sosup[i] = s[i] = s[i] - '0';
	FOR(i, 0, n)
	{
		FOR(mask, 0, 1 << n)
			if (!(mask >> i & 1)) sosup[mask] += sosup[mask ^ (1 << i)];
		for (int mask = (1 << n) - 1; mask >= 0; mask--)
			if (mask >> i & 1) sosub[mask] += sosub[mask ^ (1 << i)];
	}

	while (q--)
	{
		char t[MAXN];
		cin >> t;
		int m0 = 0, m1 = 0, mq = 0;
		FOR(i, 0, n)
		{
			if (t[n - i - 1] == '0') m0 |= (1 << i);
			else if (t[n - i - 1] == '1') m1 |= (1 << i);
			else mq |= (1 << i);
		}
		int cnt0 = __builtin_popcount(m0);
		int cnt1 = __builtin_popcount(m1);
		if (n - cnt0 - cnt1 <= BND)
		{
			int ans = s[m1];
			for (int sub = mq; sub; sub = (sub - 1) & mq)
				ans += s[m1 | sub];
			cout << ans << endl;
			continue;
		}
		if (cnt0 < cnt1)
		{
			int ans = sosup[m1];
			for (int sub = m0; sub; sub = (sub - 1) & m0)
				ans += (__builtin_popcount(sub) % 2 ? -1 : 1) * sosup[sub | m1];
			cout << ans << endl;
		}
		else
		{
			int ans = 0;
			for (int sub = m1; ; sub = (sub - 1) & m1)
			{
				ans += ((cnt1 - __builtin_popcount(sub)) % 2 ? -1 : 1) * sosub[mq | sub];
				if (!sub) break;
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	243 ms	15056 KB	Output is correct
12	Correct	274 ms	14692 KB	Output is correct
13	Correct	324 ms	13908 KB	Output is correct
14	Correct	300 ms	14032 KB	Output is correct
15	Correct	259 ms	15148 KB	Output is correct
16	Correct	318 ms	14260 KB	Output is correct
17	Correct	310 ms	14248 KB	Output is correct
18	Correct	207 ms	16236 KB	Output is correct
19	Correct	240 ms	13004 KB	Output is correct
20	Correct	253 ms	14672 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	243 ms	15056 KB	Output is correct
12	Correct	274 ms	14692 KB	Output is correct
13	Correct	324 ms	13908 KB	Output is correct
14	Correct	300 ms	14032 KB	Output is correct
15	Correct	259 ms	15148 KB	Output is correct
16	Correct	318 ms	14260 KB	Output is correct
17	Correct	310 ms	14248 KB	Output is correct
18	Correct	207 ms	16236 KB	Output is correct
19	Correct	240 ms	13004 KB	Output is correct
20	Correct	253 ms	14672 KB	Output is correct
21	Correct	262 ms	18080 KB	Output is correct
22	Correct	276 ms	18192 KB	Output is correct
23	Correct	390 ms	17348 KB	Output is correct
24	Correct	384 ms	17056 KB	Output is correct
25	Correct	284 ms	19104 KB	Output is correct
26	Correct	378 ms	17640 KB	Output is correct
27	Correct	399 ms	17684 KB	Output is correct
28	Correct	217 ms	20028 KB	Output is correct
29	Correct	261 ms	16076 KB	Output is correct
30	Correct	289 ms	18216 KB	Output is correct
31	Correct	358 ms	18052 KB	Output is correct
32	Correct	379 ms	18116 KB	Output is correct
33	Correct	297 ms	16964 KB	Output is correct
34	Correct	365 ms	17056 KB	Output is correct
35	Correct	375 ms	17648 KB	Output is correct
36	Correct	227 ms	16068 KB	Output is correct
37	Correct	259 ms	18172 KB	Output is correct
38	Correct	277 ms	16068 KB	Output is correct
39	Correct	359 ms	17220 KB	Output is correct
40	Correct	363 ms	17132 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	70 ms	11848 KB	Output is correct
12	Correct	68 ms	11800 KB	Output is correct
13	Correct	90 ms	11720 KB	Output is correct
14	Correct	103 ms	11716 KB	Output is correct
15	Correct	72 ms	11860 KB	Output is correct
16	Correct	108 ms	11716 KB	Output is correct
17	Correct	131 ms	11992 KB	Output is correct
18	Correct	73 ms	11976 KB	Output is correct
19	Correct	70 ms	11604 KB	Output is correct
20	Correct	71 ms	11844 KB	Output is correct
21	Correct	87 ms	11848 KB	Output is correct
22	Correct	99 ms	11724 KB	Output is correct
23	Correct	73 ms	11716 KB	Output is correct
24	Correct	109 ms	11716 KB	Output is correct
25	Correct	118 ms	11732 KB	Output is correct
26	Correct	65 ms	11592 KB	Output is correct
27	Correct	68 ms	11808 KB	Output is correct
28	Correct	70 ms	11600 KB	Output is correct
29	Correct	90 ms	11800 KB	Output is correct
30	Correct	119 ms	11732 KB	Output is correct
31	Correct	76 ms	11720 KB	Output is correct
32	Correct	103 ms	11788 KB	Output is correct
33	Correct	110 ms	11732 KB	Output is correct
34	Correct	64 ms	11600 KB	Output is correct
35	Correct	96 ms	11732 KB	Output is correct
36	Correct	98 ms	11824 KB	Output is correct
37	Correct	97 ms	11720 KB	Output is correct
38	Correct	103 ms	11720 KB	Output is correct
39	Correct	117 ms	11720 KB	Output is correct
40	Correct	96 ms	11760 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	243 ms	15056 KB	Output is correct
12	Correct	274 ms	14692 KB	Output is correct
13	Correct	324 ms	13908 KB	Output is correct
14	Correct	300 ms	14032 KB	Output is correct
15	Correct	259 ms	15148 KB	Output is correct
16	Correct	318 ms	14260 KB	Output is correct
17	Correct	310 ms	14248 KB	Output is correct
18	Correct	207 ms	16236 KB	Output is correct
19	Correct	240 ms	13004 KB	Output is correct
20	Correct	253 ms	14672 KB	Output is correct
21	Correct	262 ms	18080 KB	Output is correct
22	Correct	276 ms	18192 KB	Output is correct
23	Correct	390 ms	17348 KB	Output is correct
24	Correct	384 ms	17056 KB	Output is correct
25	Correct	284 ms	19104 KB	Output is correct
26	Correct	378 ms	17640 KB	Output is correct
27	Correct	399 ms	17684 KB	Output is correct
28	Correct	217 ms	20028 KB	Output is correct
29	Correct	261 ms	16076 KB	Output is correct
30	Correct	289 ms	18216 KB	Output is correct
31	Correct	358 ms	18052 KB	Output is correct
32	Correct	379 ms	18116 KB	Output is correct
33	Correct	297 ms	16964 KB	Output is correct
34	Correct	365 ms	17056 KB	Output is correct
35	Correct	375 ms	17648 KB	Output is correct
36	Correct	227 ms	16068 KB	Output is correct
37	Correct	259 ms	18172 KB	Output is correct
38	Correct	277 ms	16068 KB	Output is correct
39	Correct	359 ms	17220 KB	Output is correct
40	Correct	363 ms	17132 KB	Output is correct
41	Correct	70 ms	11848 KB	Output is correct
42	Correct	68 ms	11800 KB	Output is correct
43	Correct	90 ms	11720 KB	Output is correct
44	Correct	103 ms	11716 KB	Output is correct
45	Correct	72 ms	11860 KB	Output is correct
46	Correct	108 ms	11716 KB	Output is correct
47	Correct	131 ms	11992 KB	Output is correct
48	Correct	73 ms	11976 KB	Output is correct
49	Correct	70 ms	11604 KB	Output is correct
50	Correct	71 ms	11844 KB	Output is correct
51	Correct	87 ms	11848 KB	Output is correct
52	Correct	99 ms	11724 KB	Output is correct
53	Correct	73 ms	11716 KB	Output is correct
54	Correct	109 ms	11716 KB	Output is correct
55	Correct	118 ms	11732 KB	Output is correct
56	Correct	65 ms	11592 KB	Output is correct
57	Correct	68 ms	11808 KB	Output is correct
58	Correct	70 ms	11600 KB	Output is correct
59	Correct	90 ms	11800 KB	Output is correct
60	Correct	119 ms	11732 KB	Output is correct
61	Correct	76 ms	11720 KB	Output is correct
62	Correct	103 ms	11788 KB	Output is correct
63	Correct	110 ms	11732 KB	Output is correct
64	Correct	64 ms	11600 KB	Output is correct
65	Correct	96 ms	11732 KB	Output is correct
66	Correct	98 ms	11824 KB	Output is correct
67	Correct	97 ms	11720 KB	Output is correct
68	Correct	103 ms	11720 KB	Output is correct
69	Correct	117 ms	11720 KB	Output is correct
70	Correct	96 ms	11760 KB	Output is correct
71	Correct	433 ms	36072 KB	Output is correct
72	Correct	531 ms	36296 KB	Output is correct
73	Correct	966 ms	34840 KB	Output is correct
74	Correct	949 ms	35104 KB	Output is correct
75	Correct	462 ms	37056 KB	Output is correct
76	Correct	1312 ms	35472 KB	Output is correct
77	Correct	1378 ms	35264 KB	Output is correct
78	Correct	299 ms	39164 KB	Output is correct
79	Correct	400 ms	33176 KB	Output is correct
80	Correct	470 ms	36292 KB	Output is correct
81	Correct	733 ms	36188 KB	Output is correct
82	Correct	1116 ms	35056 KB	Output is correct
83	Correct	533 ms	34312 KB	Output is correct
84	Correct	1283 ms	35136 KB	Output is correct
85	Correct	1377 ms	35520 KB	Output is correct
86	Correct	297 ms	33044 KB	Output is correct
87	Correct	423 ms	36148 KB	Output is correct
88	Correct	399 ms	33132 KB	Output is correct
89	Correct	814 ms	34852 KB	Output is correct
90	Correct	1450 ms	35292 KB	Output is correct
91	Correct	531 ms	34328 KB	Output is correct
92	Correct	1167 ms	35468 KB	Output is correct
93	Correct	1293 ms	35372 KB	Output is correct
94	Correct	280 ms	33088 KB	Output is correct
95	Correct	913 ms	35216 KB	Output is correct
96	Correct	920 ms	35292 KB	Output is correct
97	Correct	930 ms	35268 KB	Output is correct
98	Correct	931 ms	35240 KB	Output is correct
99	Correct	952 ms	35208 KB	Output is correct
100	Correct	924 ms	35328 KB	Output is correct

답안 #391295

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