답안 #860636

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860636	2023-10-13T15:04:40 Z	phoenix0423	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	554 ms	38008 KB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1<<20 + 5;
const int sqrtn = 500;
int super[maxn], sub[maxn];
//sos dp + sqrt-sort technique(pigeonhole principle)

int main(void){
	fastio;
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	for(int i = 0; i < (1 << l); i++) sub[i] = super[i] = s[i] - '0';
	for(int i = 0; i < l; i++){
		for(int mask = 0; mask < (1 << l); mask++){
			if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
			else super[mask] += super[mask ^ (1 << i)];
		}
	}
	while(q--){
		string t;
		cin>>t;
		int cnt0 = 0, cnt1 = 0, cnt2 = 0;
		int a = 0, b = 0, c = 0; //a = 0, b = 1, c = 2
		for(int i = 0; i < l; i++){
			char x = t[i];
			if(x == '0') cnt0++, a |= (1 << (l - i - 1));
			else if(x == '1') cnt1++, b |= (1 << (l - i - 1));
			else cnt2++, c |= (1 << (l - i - 1));
		}
		int ans = 0;
		if(cnt2 <= cnt0 && cnt2 <= cnt1){
			for(int mask = c; mask > 0; mask = (mask - 1) & c){
				ans += s[mask | b] - '0';
			}
			ans += s[b] - '0';
		}
		else if(cnt0 <= cnt1){
			for(int mask = a; mask > 0; mask = (mask - 1) & a){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * super[mask | b];
			}
			ans += super[b];
		}
		else{
			for(int mask = b; mask > 0; mask = (mask - 1) & b){
				ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * sub[c | (b ^ mask)];
			}
			ans += sub[c | b];
		}
		cout<<ans<<"\n";
	}
}

Compilation message

snake_escaping.cpp:11:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   11 | const int maxn = 1<<20 + 5;
      |                     ~~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2480 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	159 ms	6480 KB	Output is correct
12	Correct	170 ms	6020 KB	Output is correct
13	Correct	192 ms	5200 KB	Output is correct
14	Correct	226 ms	5352 KB	Output is correct
15	Correct	177 ms	6480 KB	Output is correct
16	Correct	203 ms	5460 KB	Output is correct
17	Correct	204 ms	6044 KB	Output is correct
18	Correct	137 ms	7508 KB	Output is correct
19	Correct	155 ms	4432 KB	Output is correct
20	Correct	168 ms	5984 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2480 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	159 ms	6480 KB	Output is correct
12	Correct	170 ms	6020 KB	Output is correct
13	Correct	192 ms	5200 KB	Output is correct
14	Correct	226 ms	5352 KB	Output is correct
15	Correct	177 ms	6480 KB	Output is correct
16	Correct	203 ms	5460 KB	Output is correct
17	Correct	204 ms	6044 KB	Output is correct
18	Correct	137 ms	7508 KB	Output is correct
19	Correct	155 ms	4432 KB	Output is correct
20	Correct	168 ms	5984 KB	Output is correct
21	Correct	195 ms	6524 KB	Output is correct
22	Correct	205 ms	6996 KB	Output is correct
23	Correct	228 ms	5712 KB	Output is correct
24	Correct	219 ms	5532 KB	Output is correct
25	Correct	203 ms	7376 KB	Output is correct
26	Correct	242 ms	6228 KB	Output is correct
27	Correct	233 ms	5988 KB	Output is correct
28	Correct	147 ms	8528 KB	Output is correct
29	Correct	175 ms	4532 KB	Output is correct
30	Correct	190 ms	6480 KB	Output is correct
31	Correct	228 ms	6484 KB	Output is correct
32	Correct	289 ms	6344 KB	Output is correct
33	Correct	194 ms	5204 KB	Output is correct
34	Correct	228 ms	5500 KB	Output is correct
35	Correct	236 ms	6228 KB	Output is correct
36	Correct	141 ms	4368 KB	Output is correct
37	Correct	175 ms	6376 KB	Output is correct
38	Correct	218 ms	4436 KB	Output is correct
39	Correct	216 ms	5664 KB	Output is correct
40	Correct	211 ms	5460 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2480 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	37 ms	12288 KB	Output is correct
12	Correct	33 ms	13620 KB	Output is correct
13	Correct	37 ms	13568 KB	Output is correct
14	Correct	55 ms	13868 KB	Output is correct
15	Correct	34 ms	13808 KB	Output is correct
16	Correct	44 ms	13564 KB	Output is correct
17	Correct	39 ms	13556 KB	Output is correct
18	Correct	30 ms	13764 KB	Output is correct
19	Correct	35 ms	13900 KB	Output is correct
20	Correct	34 ms	13808 KB	Output is correct
21	Correct	37 ms	13808 KB	Output is correct
22	Correct	46 ms	13552 KB	Output is correct
23	Correct	34 ms	13556 KB	Output is correct
24	Correct	44 ms	13840 KB	Output is correct
25	Correct	49 ms	13560 KB	Output is correct
26	Correct	30 ms	13556 KB	Output is correct
27	Correct	33 ms	13808 KB	Output is correct
28	Correct	36 ms	13552 KB	Output is correct
29	Correct	35 ms	13672 KB	Output is correct
30	Correct	39 ms	13708 KB	Output is correct
31	Correct	39 ms	13592 KB	Output is correct
32	Correct	44 ms	13708 KB	Output is correct
33	Correct	40 ms	13556 KB	Output is correct
34	Correct	28 ms	13592 KB	Output is correct
35	Correct	43 ms	13556 KB	Output is correct
36	Correct	50 ms	13524 KB	Output is correct
37	Correct	38 ms	13552 KB	Output is correct
38	Correct	37 ms	13556 KB	Output is correct
39	Correct	39 ms	13624 KB	Output is correct
40	Correct	37 ms	13556 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2480 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	159 ms	6480 KB	Output is correct
12	Correct	170 ms	6020 KB	Output is correct
13	Correct	192 ms	5200 KB	Output is correct
14	Correct	226 ms	5352 KB	Output is correct
15	Correct	177 ms	6480 KB	Output is correct
16	Correct	203 ms	5460 KB	Output is correct
17	Correct	204 ms	6044 KB	Output is correct
18	Correct	137 ms	7508 KB	Output is correct
19	Correct	155 ms	4432 KB	Output is correct
20	Correct	168 ms	5984 KB	Output is correct
21	Correct	195 ms	6524 KB	Output is correct
22	Correct	205 ms	6996 KB	Output is correct
23	Correct	228 ms	5712 KB	Output is correct
24	Correct	219 ms	5532 KB	Output is correct
25	Correct	203 ms	7376 KB	Output is correct
26	Correct	242 ms	6228 KB	Output is correct
27	Correct	233 ms	5988 KB	Output is correct
28	Correct	147 ms	8528 KB	Output is correct
29	Correct	175 ms	4532 KB	Output is correct
30	Correct	190 ms	6480 KB	Output is correct
31	Correct	228 ms	6484 KB	Output is correct
32	Correct	289 ms	6344 KB	Output is correct
33	Correct	194 ms	5204 KB	Output is correct
34	Correct	228 ms	5500 KB	Output is correct
35	Correct	236 ms	6228 KB	Output is correct
36	Correct	141 ms	4368 KB	Output is correct
37	Correct	175 ms	6376 KB	Output is correct
38	Correct	218 ms	4436 KB	Output is correct
39	Correct	216 ms	5664 KB	Output is correct
40	Correct	211 ms	5460 KB	Output is correct
41	Correct	37 ms	12288 KB	Output is correct
42	Correct	33 ms	13620 KB	Output is correct
43	Correct	37 ms	13568 KB	Output is correct
44	Correct	55 ms	13868 KB	Output is correct
45	Correct	34 ms	13808 KB	Output is correct
46	Correct	44 ms	13564 KB	Output is correct
47	Correct	39 ms	13556 KB	Output is correct
48	Correct	30 ms	13764 KB	Output is correct
49	Correct	35 ms	13900 KB	Output is correct
50	Correct	34 ms	13808 KB	Output is correct
51	Correct	37 ms	13808 KB	Output is correct
52	Correct	46 ms	13552 KB	Output is correct
53	Correct	34 ms	13556 KB	Output is correct
54	Correct	44 ms	13840 KB	Output is correct
55	Correct	49 ms	13560 KB	Output is correct
56	Correct	30 ms	13556 KB	Output is correct
57	Correct	33 ms	13808 KB	Output is correct
58	Correct	36 ms	13552 KB	Output is correct
59	Correct	35 ms	13672 KB	Output is correct
60	Correct	39 ms	13708 KB	Output is correct
61	Correct	39 ms	13592 KB	Output is correct
62	Correct	44 ms	13708 KB	Output is correct
63	Correct	40 ms	13556 KB	Output is correct
64	Correct	28 ms	13592 KB	Output is correct
65	Correct	43 ms	13556 KB	Output is correct
66	Correct	50 ms	13524 KB	Output is correct
67	Correct	38 ms	13552 KB	Output is correct
68	Correct	37 ms	13556 KB	Output is correct
69	Correct	39 ms	13624 KB	Output is correct
70	Correct	37 ms	13556 KB	Output is correct
71	Correct	292 ms	36196 KB	Output is correct
72	Correct	296 ms	28640 KB	Output is correct
73	Correct	349 ms	27120 KB	Output is correct
74	Correct	554 ms	27120 KB	Output is correct
75	Correct	310 ms	34692 KB	Output is correct
76	Correct	511 ms	28008 KB	Output is correct
77	Correct	422 ms	27544 KB	Output is correct
78	Correct	219 ms	35516 KB	Output is correct
79	Correct	289 ms	25328 KB	Output is correct
80	Correct	291 ms	38008 KB	Output is correct
81	Correct	368 ms	32324 KB	Output is correct
82	Correct	545 ms	27824 KB	Output is correct
83	Correct	290 ms	26516 KB	Output is correct
84	Correct	400 ms	27480 KB	Output is correct
85	Correct	435 ms	27536 KB	Output is correct
86	Correct	206 ms	25072 KB	Output is correct
87	Correct	272 ms	31496 KB	Output is correct
88	Correct	274 ms	25076 KB	Output is correct
89	Correct	323 ms	25408 KB	Output is correct
90	Correct	382 ms	16204 KB	Output is correct
91	Correct	301 ms	15088 KB	Output is correct
92	Correct	446 ms	19884 KB	Output is correct
93	Correct	402 ms	18672 KB	Output is correct
94	Correct	189 ms	13932 KB	Output is correct
95	Correct	401 ms	21708 KB	Output is correct
96	Correct	368 ms	19812 KB	Output is correct
97	Correct	357 ms	19680 KB	Output is correct
98	Correct	368 ms	20208 KB	Output is correct
99	Correct	372 ms	20632 KB	Output is correct
100	Correct	363 ms	22016 KB	Output is correct

답안 #860636

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