Submission #376465

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376465	2021-03-11T14:08:36 Z	astoria	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	2000 ms	16492 KB

snake_escaping

#include "bits/stdc++.h"
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int l,q,n;
	cin>>l>>q; n=1<<l;
	string s; cin>>s;
	int tox[n];
	for(int i=0; i<n; i++) tox[i] = s[i]-'0';
	
	int pw[l+5]; pw[0]=1;
	int k=1; for(int i=1; i<=l; i++){ k*=3; pw[i]=k;}
	int ans[k]; memset(ans,0,sizeof(ans));
	
	for(int ahc=0; ahc<k; ahc++){
		vector<int> v; int cr=ahc;
		for(int j=0; j<l; j++){
			v.push_back(cr%3); cr/=3;
		}
		for(int i=0; i<n; i++){
			bitset<10> b(i); bool f=1;
			for(int j=0; j<l; j++){
				if(v[j]!=2 && (b[j]!=v[j])){ f=0; break;}
			}
			if(f) ans[ahc] += tox[i];
		}
	}
	
	for(int ahc=0; ahc<q; ahc++){
		string s; cin>>s;
		int qr=0;
		for(int i=0; i<l; i++){
			int pwer = l-i-1;
			if(s[i]=='1') qr += (pw[pwer]);
			if(s[i]=='?') qr += (2*pw[pwer]);
		}
		cout<<ans[qr]<<"\n";
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	490 ms	620 KB	Output is correct
2	Correct	445 ms	748 KB	Output is correct
3	Correct	446 ms	748 KB	Output is correct
4	Correct	449 ms	632 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	442 ms	632 KB	Output is correct
7	Correct	445 ms	632 KB	Output is correct
8	Correct	451 ms	696 KB	Output is correct
9	Correct	444 ms	692 KB	Output is correct
10	Correct	443 ms	632 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	490 ms	620 KB	Output is correct
2	Correct	445 ms	748 KB	Output is correct
3	Correct	446 ms	748 KB	Output is correct
4	Correct	449 ms	632 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	442 ms	632 KB	Output is correct
7	Correct	445 ms	632 KB	Output is correct
8	Correct	451 ms	696 KB	Output is correct
9	Correct	444 ms	692 KB	Output is correct
10	Correct	443 ms	632 KB	Output is correct
11	Correct	705 ms	15356 KB	Output is correct
12	Correct	690 ms	15084 KB	Output is correct
13	Correct	696 ms	14316 KB	Output is correct
14	Correct	703 ms	14332 KB	Output is correct
15	Correct	695 ms	15484 KB	Output is correct
16	Correct	720 ms	14700 KB	Output is correct
17	Correct	728 ms	14444 KB	Output is correct
18	Correct	666 ms	16492 KB	Output is correct
19	Correct	702 ms	13548 KB	Output is correct
20	Correct	697 ms	15084 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	490 ms	620 KB	Output is correct
2	Correct	445 ms	748 KB	Output is correct
3	Correct	446 ms	748 KB	Output is correct
4	Correct	449 ms	632 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	442 ms	632 KB	Output is correct
7	Correct	445 ms	632 KB	Output is correct
8	Correct	451 ms	696 KB	Output is correct
9	Correct	444 ms	692 KB	Output is correct
10	Correct	443 ms	632 KB	Output is correct
11	Correct	705 ms	15356 KB	Output is correct
12	Correct	690 ms	15084 KB	Output is correct
13	Correct	696 ms	14316 KB	Output is correct
14	Correct	703 ms	14332 KB	Output is correct
15	Correct	695 ms	15484 KB	Output is correct
16	Correct	720 ms	14700 KB	Output is correct
17	Correct	728 ms	14444 KB	Output is correct
18	Correct	666 ms	16492 KB	Output is correct
19	Correct	702 ms	13548 KB	Output is correct
20	Correct	697 ms	15084 KB	Output is correct
21	Execution timed out	2076 ms	6636 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	490 ms	620 KB	Output is correct
2	Correct	445 ms	748 KB	Output is correct
3	Correct	446 ms	748 KB	Output is correct
4	Correct	449 ms	632 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	442 ms	632 KB	Output is correct
7	Correct	445 ms	632 KB	Output is correct
8	Correct	451 ms	696 KB	Output is correct
9	Correct	444 ms	692 KB	Output is correct
10	Correct	443 ms	632 KB	Output is correct
11	Runtime error	14 ms	12400 KB	Execution killed with signal 7
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	490 ms	620 KB	Output is correct
2	Correct	445 ms	748 KB	Output is correct
3	Correct	446 ms	748 KB	Output is correct
4	Correct	449 ms	632 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	442 ms	632 KB	Output is correct
7	Correct	445 ms	632 KB	Output is correct
8	Correct	451 ms	696 KB	Output is correct
9	Correct	444 ms	692 KB	Output is correct
10	Correct	443 ms	632 KB	Output is correct
11	Correct	705 ms	15356 KB	Output is correct
12	Correct	690 ms	15084 KB	Output is correct
13	Correct	696 ms	14316 KB	Output is correct
14	Correct	703 ms	14332 KB	Output is correct
15	Correct	695 ms	15484 KB	Output is correct
16	Correct	720 ms	14700 KB	Output is correct
17	Correct	728 ms	14444 KB	Output is correct
18	Correct	666 ms	16492 KB	Output is correct
19	Correct	702 ms	13548 KB	Output is correct
20	Correct	697 ms	15084 KB	Output is correct
21	Execution timed out	2076 ms	6636 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-