oj.uz

Submission #535322

# Submission time Handle Problem Language Result Execution time Memory
535322 2022-03-10T02:43:58 Z amunduzbaev Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 996 ms 65536 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 20;
int dp[2][1 << N][20];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	string s; cin>>s;
	vector<int> a(1 << n);
	for(int i=0;i<(1 << n);i++) a[i] = s[i] - '0';
	//~ for(int i=0;i<(1 << n);i++){
		//~ for(int j=0;j<n;j++) cout<<(i >> j & 1);
		//~ cout<<" : "<<a[i]<<"\n";
	//~ }
	
	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 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 464 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 472 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 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 464 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 472 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 568 ms 15312 KB Output is correct
12 Correct 616 ms 14924 KB Output is correct
13 Correct 397 ms 14132 KB Output is correct
14 Correct 395 ms 14212 KB Output is correct
15 Correct 936 ms 15196 KB Output is correct
16 Correct 513 ms 14420 KB Output is correct
17 Correct 502 ms 14416 KB Output is correct
18 Correct 179 ms 16204 KB Output is correct
19 Correct 222 ms 13212 KB Output is correct
20 Correct 588 ms 14908 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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 464 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 472 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 568 ms 15312 KB Output is correct
12 Correct 616 ms 14924 KB Output is correct
13 Correct 397 ms 14132 KB Output is correct
14 Correct 395 ms 14212 KB Output is correct
15 Correct 936 ms 15196 KB Output is correct
16 Correct 513 ms 14420 KB Output is correct
17 Correct 502 ms 14416 KB Output is correct
18 Correct 179 ms 16204 KB Output is correct
19 Correct 222 ms 13212 KB Output is correct
20 Correct 588 ms 14908 KB Output is correct
21 Correct 306 ms 19376 KB Output is correct
22 Correct 864 ms 19448 KB Output is correct
23 Correct 567 ms 18556 KB Output is correct
24 Correct 517 ms 18280 KB Output is correct
25 Correct 464 ms 20500 KB Output is correct
26 Correct 685 ms 18796 KB Output is correct
27 Correct 647 ms 18868 KB Output is correct
28 Correct 208 ms 21340 KB Output is correct
29 Correct 259 ms 17384 KB Output is correct
30 Correct 566 ms 19484 KB Output is correct
31 Correct 996 ms 19452 KB Output is correct
32 Correct 653 ms 19276 KB Output is correct
33 Correct 414 ms 18244 KB Output is correct
34 Correct 505 ms 18376 KB Output is correct
35 Correct 651 ms 18928 KB Output is correct
36 Correct 225 ms 17420 KB Output is correct
37 Correct 973 ms 19580 KB Output is correct
38 Correct 276 ms 17356 KB Output is correct
39 Correct 559 ms 18508 KB Output is correct
40 Correct 492 ms 18272 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory 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 464 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 472 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 71 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 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 464 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 472 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 568 ms 15312 KB Output is correct
12 Correct 616 ms 14924 KB Output is correct
13 Correct 397 ms 14132 KB Output is correct
14 Correct 395 ms 14212 KB Output is correct
15 Correct 936 ms 15196 KB Output is correct
16 Correct 513 ms 14420 KB Output is correct
17 Correct 502 ms 14416 KB Output is correct
18 Correct 179 ms 16204 KB Output is correct
19 Correct 222 ms 13212 KB Output is correct
20 Correct 588 ms 14908 KB Output is correct
21 Correct 306 ms 19376 KB Output is correct
22 Correct 864 ms 19448 KB Output is correct
23 Correct 567 ms 18556 KB Output is correct
24 Correct 517 ms 18280 KB Output is correct
25 Correct 464 ms 20500 KB Output is correct
26 Correct 685 ms 18796 KB Output is correct
27 Correct 647 ms 18868 KB Output is correct
28 Correct 208 ms 21340 KB Output is correct
29 Correct 259 ms 17384 KB Output is correct
30 Correct 566 ms 19484 KB Output is correct
31 Correct 996 ms 19452 KB Output is correct
32 Correct 653 ms 19276 KB Output is correct
33 Correct 414 ms 18244 KB Output is correct
34 Correct 505 ms 18376 KB Output is correct
35 Correct 651 ms 18928 KB Output is correct
36 Correct 225 ms 17420 KB Output is correct
37 Correct 973 ms 19580 KB Output is correct
38 Correct 276 ms 17356 KB Output is correct
39 Correct 559 ms 18508 KB Output is correct
40 Correct 492 ms 18272 KB Output is correct
41 Runtime error 71 ms 65536 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -