답안 #404597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404597	2021-05-14T17:25:54 Z	Antekb	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	1459 ms	43472 KB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
const int L=20;
int tab[1<<L], pod[1<<L], nad[1<<L];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
	int l, q;
	cin>>l>>q;
	string s;
	cin>>s;
	int n=s.size();
	for(int i=0; i<n; i++)tab[i]=pod[i]=nad[i]=s[i]-'0';
	for(int j=0; j<l; j++){
		for(int i=0; i<n; i++)
		{
			if(i&(1<<j))pod[i]+=pod[i^(1<<j)];
			else nad[i]+=nad[i^(1<<j)];
		}
	}
	/*for(int i=0; i<n; i++){
		cout<<i<<" "<<pod[i]<<" "<<nad[i]<<"\n";
	}*/
	for(int i=0; i<q; i++){
		int c1=0, c2=0, c3=0;
		string t;
		cin>>t;
		reverse(t.begin(), t.end());
		for(int j=0; j<l; j++){
			if(t[j]=='0')c1++;
			else if(t[j]=='1')c2++;
			else c3++;
		}
		if(c1==min({c1, c2, c3})){
			int x=0, y=0, ans=0;
			for(int j=0; j<l; j++)if(t[j]=='0')x+=(1<<j);
			for(int j=0; j<l; j++)if(t[j]=='1')y+=(1<<j);
			for(int j=x; ; j=(j-1)&x){
				//cout<<y+j<<" "<<bitset<3>(y+j)<<" ";
				if(__builtin_popcount(j)&1){
					ans-=nad[y+j];
				}
				else ans+=nad[y+j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
		else if(c2==min({c1, c2, c3})){
			int x=0, y=0, ans=0;
			for(int j=0; j<l; j++)if(t[j]=='1')x+=(1<<j);
			for(int j=0; j<l; j++)if(t[j]!='0')y+=(1<<j);
			for(int j=x; ; j=(j-1)&x){
				//cout<<y+j<<" "<<bitset<3>(y+j)<<" ";
				if(__builtin_popcount(j)&1){
					ans-=pod[y-j];
				}
				else ans+=pod[y-j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
		else{
			int ans=0, x=0, y=0;
			for(int j=0; j<l;j ++){
				if(t[j]=='?')x+=(1<<j);
				if(t[j]=='1')y+=(1<<j);
			}
			for(int j=x;  ; j=(j-1)&x){
				ans+=tab[y+j];
				if(j==0)break;
			}
			cout<<ans<<"\n";
		}
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	2 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	2 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	388 KB	Output is correct
2	Correct	2 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	2 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	297 ms	15032 KB	Output is correct
12	Correct	315 ms	14900 KB	Output is correct
13	Correct	347 ms	14028 KB	Output is correct
14	Correct	395 ms	14052 KB	Output is correct
15	Correct	347 ms	15048 KB	Output is correct
16	Correct	386 ms	14256 KB	Output is correct
17	Correct	413 ms	14248 KB	Output is correct
18	Correct	227 ms	16068 KB	Output is correct
19	Correct	257 ms	13048 KB	Output is correct
20	Correct	338 ms	14784 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	2 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	2 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	297 ms	15032 KB	Output is correct
12	Correct	315 ms	14900 KB	Output is correct
13	Correct	347 ms	14028 KB	Output is correct
14	Correct	395 ms	14052 KB	Output is correct
15	Correct	347 ms	15048 KB	Output is correct
16	Correct	386 ms	14256 KB	Output is correct
17	Correct	413 ms	14248 KB	Output is correct
18	Correct	227 ms	16068 KB	Output is correct
19	Correct	257 ms	13048 KB	Output is correct
20	Correct	338 ms	14784 KB	Output is correct
21	Correct	370 ms	18132 KB	Output is correct
22	Correct	389 ms	18324 KB	Output is correct
23	Correct	422 ms	17224 KB	Output is correct
24	Correct	529 ms	17132 KB	Output is correct
25	Correct	408 ms	19140 KB	Output is correct
26	Correct	483 ms	17640 KB	Output is correct
27	Correct	462 ms	17516 KB	Output is correct
28	Correct	248 ms	20132 KB	Output is correct
29	Correct	282 ms	16144 KB	Output is correct
30	Correct	409 ms	18328 KB	Output is correct
31	Correct	482 ms	18268 KB	Output is correct
32	Correct	553 ms	18260 KB	Output is correct
33	Correct	361 ms	17132 KB	Output is correct
34	Correct	512 ms	17124 KB	Output is correct
35	Correct	466 ms	17676 KB	Output is correct
36	Correct	265 ms	16068 KB	Output is correct
37	Correct	424 ms	18112 KB	Output is correct
38	Correct	300 ms	16100 KB	Output is correct
39	Correct	411 ms	17300 KB	Output is correct
40	Correct	518 ms	17160 KB	Output is correct

Subtask #4
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	2 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	2 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	66 ms	16080 KB	Output is correct
12	Correct	63 ms	15968 KB	Output is correct
13	Correct	73 ms	15944 KB	Output is correct
14	Correct	92 ms	15900 KB	Output is correct
15	Correct	62 ms	16044 KB	Output is correct
16	Correct	103 ms	16036 KB	Output is correct
17	Correct	92 ms	15936 KB	Output is correct
18	Correct	52 ms	16176 KB	Output is correct
19	Correct	54 ms	15872 KB	Output is correct
20	Correct	62 ms	16028 KB	Output is correct
21	Correct	78 ms	16076 KB	Output is correct
22	Correct	87 ms	15968 KB	Output is correct
23	Correct	62 ms	15972 KB	Output is correct
24	Correct	101 ms	15928 KB	Output is correct
25	Correct	100 ms	15980 KB	Output is correct
26	Correct	50 ms	15888 KB	Output is correct
27	Correct	60 ms	15976 KB	Output is correct
28	Correct	57 ms	15916 KB	Output is correct
29	Correct	69 ms	15912 KB	Output is correct
30	Correct	71 ms	15944 KB	Output is correct
31	Correct	80 ms	15960 KB	Output is correct
32	Correct	110 ms	15968 KB	Output is correct
33	Correct	94 ms	16012 KB	Output is correct
34	Correct	49 ms	15840 KB	Output is correct
35	Correct	77 ms	15944 KB	Output is correct
36	Correct	81 ms	15928 KB	Output is correct
37	Correct	80 ms	16040 KB	Output is correct
38	Correct	83 ms	15944 KB	Output is correct
39	Correct	100 ms	15928 KB	Output is correct
40	Correct	84 ms	16048 KB	Output is correct

Subtask #5
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	2 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	2 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	297 ms	15032 KB	Output is correct
12	Correct	315 ms	14900 KB	Output is correct
13	Correct	347 ms	14028 KB	Output is correct
14	Correct	395 ms	14052 KB	Output is correct
15	Correct	347 ms	15048 KB	Output is correct
16	Correct	386 ms	14256 KB	Output is correct
17	Correct	413 ms	14248 KB	Output is correct
18	Correct	227 ms	16068 KB	Output is correct
19	Correct	257 ms	13048 KB	Output is correct
20	Correct	338 ms	14784 KB	Output is correct
21	Correct	370 ms	18132 KB	Output is correct
22	Correct	389 ms	18324 KB	Output is correct
23	Correct	422 ms	17224 KB	Output is correct
24	Correct	529 ms	17132 KB	Output is correct
25	Correct	408 ms	19140 KB	Output is correct
26	Correct	483 ms	17640 KB	Output is correct
27	Correct	462 ms	17516 KB	Output is correct
28	Correct	248 ms	20132 KB	Output is correct
29	Correct	282 ms	16144 KB	Output is correct
30	Correct	409 ms	18328 KB	Output is correct
31	Correct	482 ms	18268 KB	Output is correct
32	Correct	553 ms	18260 KB	Output is correct
33	Correct	361 ms	17132 KB	Output is correct
34	Correct	512 ms	17124 KB	Output is correct
35	Correct	466 ms	17676 KB	Output is correct
36	Correct	265 ms	16068 KB	Output is correct
37	Correct	424 ms	18112 KB	Output is correct
38	Correct	300 ms	16100 KB	Output is correct
39	Correct	411 ms	17300 KB	Output is correct
40	Correct	518 ms	17160 KB	Output is correct
41	Correct	66 ms	16080 KB	Output is correct
42	Correct	63 ms	15968 KB	Output is correct
43	Correct	73 ms	15944 KB	Output is correct
44	Correct	92 ms	15900 KB	Output is correct
45	Correct	62 ms	16044 KB	Output is correct
46	Correct	103 ms	16036 KB	Output is correct
47	Correct	92 ms	15936 KB	Output is correct
48	Correct	52 ms	16176 KB	Output is correct
49	Correct	54 ms	15872 KB	Output is correct
50	Correct	62 ms	16028 KB	Output is correct
51	Correct	78 ms	16076 KB	Output is correct
52	Correct	87 ms	15968 KB	Output is correct
53	Correct	62 ms	15972 KB	Output is correct
54	Correct	101 ms	15928 KB	Output is correct
55	Correct	100 ms	15980 KB	Output is correct
56	Correct	50 ms	15888 KB	Output is correct
57	Correct	60 ms	15976 KB	Output is correct
58	Correct	57 ms	15916 KB	Output is correct
59	Correct	69 ms	15912 KB	Output is correct
60	Correct	71 ms	15944 KB	Output is correct
61	Correct	80 ms	15960 KB	Output is correct
62	Correct	110 ms	15968 KB	Output is correct
63	Correct	94 ms	16012 KB	Output is correct
64	Correct	49 ms	15840 KB	Output is correct
65	Correct	77 ms	15944 KB	Output is correct
66	Correct	81 ms	15928 KB	Output is correct
67	Correct	80 ms	16040 KB	Output is correct
68	Correct	83 ms	15944 KB	Output is correct
69	Correct	100 ms	15928 KB	Output is correct
70	Correct	84 ms	16048 KB	Output is correct
71	Correct	657 ms	40296 KB	Output is correct
72	Correct	627 ms	40652 KB	Output is correct
73	Correct	833 ms	38932 KB	Output is correct
74	Correct	1214 ms	39532 KB	Output is correct
75	Correct	662 ms	41268 KB	Output is correct
76	Correct	1285 ms	39688 KB	Output is correct
77	Correct	1187 ms	39608 KB	Output is correct
78	Correct	384 ms	43472 KB	Output is correct
79	Correct	469 ms	37428 KB	Output is correct
80	Correct	631 ms	40420 KB	Output is correct
81	Correct	953 ms	40404 KB	Output is correct
82	Correct	1186 ms	39364 KB	Output is correct
83	Correct	592 ms	38500 KB	Output is correct
84	Correct	1429 ms	39368 KB	Output is correct
85	Correct	1201 ms	39508 KB	Output is correct
86	Correct	441 ms	37276 KB	Output is correct
87	Correct	617 ms	40448 KB	Output is correct
88	Correct	506 ms	37340 KB	Output is correct
89	Correct	958 ms	38972 KB	Output is correct
90	Correct	800 ms	39360 KB	Output is correct
91	Correct	635 ms	38656 KB	Output is correct
92	Correct	1459 ms	39696 KB	Output is correct
93	Correct	1215 ms	39460 KB	Output is correct
94	Correct	377 ms	37352 KB	Output is correct
95	Correct	982 ms	39472 KB	Output is correct
96	Correct	1024 ms	39376 KB	Output is correct
97	Correct	1067 ms	39452 KB	Output is correct
98	Correct	1115 ms	39456 KB	Output is correct
99	Correct	1044 ms	39444 KB	Output is correct
100	Correct	1055 ms	39372 KB	Output is correct

답안 #404597

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