Submission #376466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376466	2021-03-11T14:09:41 Z	astoria	Snake Escaping (JOI18_snake_escaping)	C++14	12 / 100	2000 ms	11292 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<13> 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	442 ms	620 KB	Output is correct
2	Correct	503 ms	620 KB	Output is correct
3	Correct	444 ms	620 KB	Output is correct
4	Correct	444 ms	620 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	441 ms	652 KB	Output is correct
7	Correct	464 ms	620 KB	Output is correct
8	Correct	442 ms	620 KB	Output is correct
9	Correct	441 ms	620 KB	Output is correct
10	Correct	448 ms	748 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	442 ms	620 KB	Output is correct
2	Correct	503 ms	620 KB	Output is correct
3	Correct	444 ms	620 KB	Output is correct
4	Correct	444 ms	620 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	441 ms	652 KB	Output is correct
7	Correct	464 ms	620 KB	Output is correct
8	Correct	442 ms	620 KB	Output is correct
9	Correct	441 ms	620 KB	Output is correct
10	Correct	448 ms	748 KB	Output is correct
11	Correct	698 ms	4716 KB	Output is correct
12	Correct	698 ms	4332 KB	Output is correct
13	Correct	703 ms	3564 KB	Output is correct
14	Correct	705 ms	3692 KB	Output is correct
15	Correct	749 ms	4716 KB	Output is correct
16	Correct	706 ms	3948 KB	Output is correct
17	Correct	758 ms	3820 KB	Output is correct
18	Correct	641 ms	5716 KB	Output is correct
19	Correct	669 ms	2668 KB	Output is correct
20	Correct	742 ms	4332 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	442 ms	620 KB	Output is correct
2	Correct	503 ms	620 KB	Output is correct
3	Correct	444 ms	620 KB	Output is correct
4	Correct	444 ms	620 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	441 ms	652 KB	Output is correct
7	Correct	464 ms	620 KB	Output is correct
8	Correct	442 ms	620 KB	Output is correct
9	Correct	441 ms	620 KB	Output is correct
10	Correct	448 ms	748 KB	Output is correct
11	Correct	698 ms	4716 KB	Output is correct
12	Correct	698 ms	4332 KB	Output is correct
13	Correct	703 ms	3564 KB	Output is correct
14	Correct	705 ms	3692 KB	Output is correct
15	Correct	749 ms	4716 KB	Output is correct
16	Correct	706 ms	3948 KB	Output is correct
17	Correct	758 ms	3820 KB	Output is correct
18	Correct	641 ms	5716 KB	Output is correct
19	Correct	669 ms	2668 KB	Output is correct
20	Correct	742 ms	4332 KB	Output is correct
21	Execution timed out	2072 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	442 ms	620 KB	Output is correct
2	Correct	503 ms	620 KB	Output is correct
3	Correct	444 ms	620 KB	Output is correct
4	Correct	444 ms	620 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	441 ms	652 KB	Output is correct
7	Correct	464 ms	620 KB	Output is correct
8	Correct	442 ms	620 KB	Output is correct
9	Correct	441 ms	620 KB	Output is correct
10	Correct	448 ms	748 KB	Output is correct
11	Runtime error	14 ms	11292 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	442 ms	620 KB	Output is correct
2	Correct	503 ms	620 KB	Output is correct
3	Correct	444 ms	620 KB	Output is correct
4	Correct	444 ms	620 KB	Output is correct
5	Correct	444 ms	620 KB	Output is correct
6	Correct	441 ms	652 KB	Output is correct
7	Correct	464 ms	620 KB	Output is correct
8	Correct	442 ms	620 KB	Output is correct
9	Correct	441 ms	620 KB	Output is correct
10	Correct	448 ms	748 KB	Output is correct
11	Correct	698 ms	4716 KB	Output is correct
12	Correct	698 ms	4332 KB	Output is correct
13	Correct	703 ms	3564 KB	Output is correct
14	Correct	705 ms	3692 KB	Output is correct
15	Correct	749 ms	4716 KB	Output is correct
16	Correct	706 ms	3948 KB	Output is correct
17	Correct	758 ms	3820 KB	Output is correct
18	Correct	641 ms	5716 KB	Output is correct
19	Correct	669 ms	2668 KB	Output is correct
20	Correct	742 ms	4332 KB	Output is correct
21	Execution timed out	2072 ms	6636 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-