oj.uz

Submission #535325

# Submission time Handle Problem Language Result Execution time Memory
535325 2022-03-10T02:56:09 Z amunduzbaev Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 340 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 20;
int dp[2][(1 << 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';
		dp[0][i] = dp[1][i] = a[i];
	}
	
	for(int i=n-1;~i;i--){
		for(int mask=(1 << n) - 1;mask<(1 << n);mask++){
			if(!(mask >> i & 1)) dp[0][mask] += dp[0][mask ^ (1 << i)];
		}
	}
	
	for(int i=n-1;~i;i--){
		for(int mask=0;mask<(1 << n);mask++){
			if(mask >> i & 1) dp[1][mask] += dp[1][mask ^ (1 << i)];
		}
	}
	
	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];
				else res += dp[t][tot];
			}
		} 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];
				else res += dp[t][tot];
			}
		}
		
		cout<<res<<"\n";
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -