Submission #535324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
535324	2022-03-10T02:53:02 Z	amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1004 ms	65536 KB

snake_escaping

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

#define ar array

const int N = 20;
int dp[2][(1 << N) + 5][N + 5];
int a[(1 << N) + 5];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	string s; cin>>s;
	for(int i=0;i<(1 << n);i++) a[i] = s[i] - '0';
	
	for(int mask=(1 << n) - 1;~mask;mask--){
		int res = a[mask];
		for(int i=n-1;~i;i--){
			if(!(mask >> i & 1)){
				res += dp[0][mask | (1 << i)][i];
			}
			dp[0][mask][i] = res;
		}
	}
	
	for(int mask=0;mask<(1 << n);mask++){
		int res = a[mask];
		for(int i=n-1;~i;i--){
			if(mask >> i & 1){
				res += dp[1][mask ^ (1 << i)][i];
			}
			dp[1][mask][i] = res;
		}
	}
	
	while(m--){
		string s; cin>>s;
		reverse(s.begin(), s.end());
		ar<int, 3> c {};
		for(int i=0;i<n;i++){
			if(s[i] == '0') c[0]++;
			if(s[i] == '1') c[1]++;
			if(s[i] == '?') c[2]++;
		}
		
		int res = 0;
		if(c[2] <= 6){
			int in = 0;
			vector<int> p;
			for(int i=0;i<n;i++){
				if(s[i] == '0' || s[i] == '1') in |= ((s[i] - '0') << i);
				else p.push_back(i);
			}
			
			for(int mask=0;mask < (1 << c[2]);mask++){
				int tot = in;
				for(int j=0;j<c[2];j++){
					if(mask >> j & 1) tot |= (1 << p[j]);
				}
				
				res += a[tot];
			}
		} 
		else if(c[0] <= 6) {
			int t = 0, in = 0;
			vector<int> p;
			for(int i=0;i<n;i++){
				if(s[i] == '1') in |= (1 << i);
				if(s[i] == '0') p.push_back(i);
			}
			
			for(int mask=0;mask < (1 << c[0]);mask++){
				int tot = in;
				for(int j=0;j<c[0];j++){
					if(mask >> j & 1) tot |= (1 << p[j]);
				}
				
				if(__builtin_popcount(mask)&1) res -= dp[t][tot][0];
				else res += dp[t][tot][0];
			}
		} else {
			int t = 1, in = (1 << n) - 1;
			vector<int> p;
			for(int i=0;i<n;i++){
				if(s[i] == '0') in ^= (1 << i);
				if(s[i] == '1') p.push_back(i);
			}
			
			for(int mask=0;mask<(1 << c[1]);mask++){
				int tot = in;
				for(int j=0;j<c[1];j++){
					if(mask >> j & 1) tot ^= (1 << p[j]);
				}
				
				if(__builtin_popcount(mask)&1) res -= dp[t][tot][0];
				else res += dp[t][tot][0];
			}
		}
		
		cout<<res<<"\n";
	}
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	567 ms	4492 KB	Output is correct
12	Correct	581 ms	4184 KB	Output is correct
13	Correct	419 ms	3404 KB	Output is correct
14	Correct	367 ms	3468 KB	Output is correct
15	Correct	952 ms	4528 KB	Output is correct
16	Correct	516 ms	3660 KB	Output is correct
17	Correct	461 ms	3628 KB	Output is correct
18	Correct	186 ms	5464 KB	Output is correct
19	Correct	210 ms	2504 KB	Output is correct
20	Correct	565 ms	4196 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	567 ms	4492 KB	Output is correct
12	Correct	581 ms	4184 KB	Output is correct
13	Correct	419 ms	3404 KB	Output is correct
14	Correct	367 ms	3468 KB	Output is correct
15	Correct	952 ms	4528 KB	Output is correct
16	Correct	516 ms	3660 KB	Output is correct
17	Correct	461 ms	3628 KB	Output is correct
18	Correct	186 ms	5464 KB	Output is correct
19	Correct	210 ms	2504 KB	Output is correct
20	Correct	565 ms	4196 KB	Output is correct
21	Correct	328 ms	6032 KB	Output is correct
22	Correct	853 ms	6064 KB	Output is correct
23	Correct	591 ms	5156 KB	Output is correct
24	Correct	507 ms	4984 KB	Output is correct
25	Correct	465 ms	7004 KB	Output is correct
26	Correct	737 ms	5432 KB	Output is correct
27	Correct	599 ms	5544 KB	Output is correct
28	Correct	213 ms	7984 KB	Output is correct
29	Correct	264 ms	3980 KB	Output is correct
30	Correct	561 ms	6048 KB	Output is correct
31	Correct	1004 ms	6012 KB	Output is correct
32	Correct	680 ms	5960 KB	Output is correct
33	Correct	419 ms	4892 KB	Output is correct
34	Correct	544 ms	4952 KB	Output is correct
35	Correct	628 ms	5380 KB	Output is correct
36	Correct	195 ms	3872 KB	Output is correct
37	Correct	954 ms	5968 KB	Output is correct
38	Correct	259 ms	3980 KB	Output is correct
39	Correct	528 ms	5124 KB	Output is correct
40	Correct	554 ms	4976 KB	Output is correct

Subtask #4
0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Runtime error	62 ms	65536 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	567 ms	4492 KB	Output is correct
12	Correct	581 ms	4184 KB	Output is correct
13	Correct	419 ms	3404 KB	Output is correct
14	Correct	367 ms	3468 KB	Output is correct
15	Correct	952 ms	4528 KB	Output is correct
16	Correct	516 ms	3660 KB	Output is correct
17	Correct	461 ms	3628 KB	Output is correct
18	Correct	186 ms	5464 KB	Output is correct
19	Correct	210 ms	2504 KB	Output is correct
20	Correct	565 ms	4196 KB	Output is correct
21	Correct	328 ms	6032 KB	Output is correct
22	Correct	853 ms	6064 KB	Output is correct
23	Correct	591 ms	5156 KB	Output is correct
24	Correct	507 ms	4984 KB	Output is correct
25	Correct	465 ms	7004 KB	Output is correct
26	Correct	737 ms	5432 KB	Output is correct
27	Correct	599 ms	5544 KB	Output is correct
28	Correct	213 ms	7984 KB	Output is correct
29	Correct	264 ms	3980 KB	Output is correct
30	Correct	561 ms	6048 KB	Output is correct
31	Correct	1004 ms	6012 KB	Output is correct
32	Correct	680 ms	5960 KB	Output is correct
33	Correct	419 ms	4892 KB	Output is correct
34	Correct	544 ms	4952 KB	Output is correct
35	Correct	628 ms	5380 KB	Output is correct
36	Correct	195 ms	3872 KB	Output is correct
37	Correct	954 ms	5968 KB	Output is correct
38	Correct	259 ms	3980 KB	Output is correct
39	Correct	528 ms	5124 KB	Output is correct
40	Correct	554 ms	4976 KB	Output is correct
41	Runtime error	62 ms	65536 KB	Execution killed with signal 9
42	Halted	0 ms	0 KB	-

Submission #535324

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0