답안 #535326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535326	2022-03-10T02:58:08 Z	amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1082 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];
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';
	s.clear();
	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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	468 KB	Output is correct
5	Correct	2 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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	468 KB	Output is correct
5	Correct	2 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	607 ms	4428 KB	Output is correct
12	Correct	601 ms	4204 KB	Output is correct
13	Correct	382 ms	3356 KB	Output is correct
14	Correct	380 ms	3508 KB	Output is correct
15	Correct	1006 ms	4556 KB	Output is correct
16	Correct	503 ms	3560 KB	Output is correct
17	Correct	497 ms	3676 KB	Output is correct
18	Correct	175 ms	5460 KB	Output is correct
19	Correct	198 ms	2404 KB	Output is correct
20	Correct	582 ms	4180 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	468 KB	Output is correct
5	Correct	2 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	607 ms	4428 KB	Output is correct
12	Correct	601 ms	4204 KB	Output is correct
13	Correct	382 ms	3356 KB	Output is correct
14	Correct	380 ms	3508 KB	Output is correct
15	Correct	1006 ms	4556 KB	Output is correct
16	Correct	503 ms	3560 KB	Output is correct
17	Correct	497 ms	3676 KB	Output is correct
18	Correct	175 ms	5460 KB	Output is correct
19	Correct	198 ms	2404 KB	Output is correct
20	Correct	582 ms	4180 KB	Output is correct
21	Correct	270 ms	5664 KB	Output is correct
22	Correct	892 ms	5784 KB	Output is correct
23	Correct	564 ms	4832 KB	Output is correct
24	Correct	494 ms	4644 KB	Output is correct
25	Correct	454 ms	6692 KB	Output is correct
26	Correct	664 ms	5148 KB	Output is correct
27	Correct	634 ms	5040 KB	Output is correct
28	Correct	194 ms	7596 KB	Output is correct
29	Correct	235 ms	3644 KB	Output is correct
30	Correct	585 ms	5800 KB	Output is correct
31	Correct	1082 ms	5936 KB	Output is correct
32	Correct	690 ms	5680 KB	Output is correct
33	Correct	402 ms	4508 KB	Output is correct
34	Correct	504 ms	4684 KB	Output is correct
35	Correct	658 ms	5132 KB	Output is correct
36	Correct	198 ms	3680 KB	Output is correct
37	Correct	1040 ms	5684 KB	Output is correct
38	Correct	260 ms	3660 KB	Output is correct
39	Correct	528 ms	4856 KB	Output is correct
40	Correct	501 ms	4692 KB	Output is correct

Subtask #4
0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	468 KB	Output is correct
5	Correct	2 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	60 ms	65536 KB	Execution killed with signal 9
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	468 KB	Output is correct
5	Correct	2 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	607 ms	4428 KB	Output is correct
12	Correct	601 ms	4204 KB	Output is correct
13	Correct	382 ms	3356 KB	Output is correct
14	Correct	380 ms	3508 KB	Output is correct
15	Correct	1006 ms	4556 KB	Output is correct
16	Correct	503 ms	3560 KB	Output is correct
17	Correct	497 ms	3676 KB	Output is correct
18	Correct	175 ms	5460 KB	Output is correct
19	Correct	198 ms	2404 KB	Output is correct
20	Correct	582 ms	4180 KB	Output is correct
21	Correct	270 ms	5664 KB	Output is correct
22	Correct	892 ms	5784 KB	Output is correct
23	Correct	564 ms	4832 KB	Output is correct
24	Correct	494 ms	4644 KB	Output is correct
25	Correct	454 ms	6692 KB	Output is correct
26	Correct	664 ms	5148 KB	Output is correct
27	Correct	634 ms	5040 KB	Output is correct
28	Correct	194 ms	7596 KB	Output is correct
29	Correct	235 ms	3644 KB	Output is correct
30	Correct	585 ms	5800 KB	Output is correct
31	Correct	1082 ms	5936 KB	Output is correct
32	Correct	690 ms	5680 KB	Output is correct
33	Correct	402 ms	4508 KB	Output is correct
34	Correct	504 ms	4684 KB	Output is correct
35	Correct	658 ms	5132 KB	Output is correct
36	Correct	198 ms	3680 KB	Output is correct
37	Correct	1040 ms	5684 KB	Output is correct
38	Correct	260 ms	3660 KB	Output is correct
39	Correct	528 ms	4856 KB	Output is correct
40	Correct	501 ms	4692 KB	Output is correct
41	Runtime error	60 ms	65536 KB	Execution killed with signal 9
42	Halted	0 ms	0 KB	-

답안 #535326

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