Submission #535325

#	Time	Username	Problem	Language	Result	Execution time	Memory
535325		amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	340 KiB

snake_escaping

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25