Submission #535335

#	Time	Username	Problem	Language	Result	Execution time	Memory
535335		amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	839 ms	65536 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int N = 20;
int dp[2][1 << N ][N];
int a[1 << N];
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<(1 << n);i++){
		char c; cin>>c;
		a[i] = c - '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;
		}
	}
	
	ar<int, 3> c {};
	int res, in, t;
	vector<int> p;
	while(m--){
		string s; cin>>s;
		reverse(s.begin(), s.end());
		c[0] = c[1] = c[2] = 0;
		for(int i=0;i<n;i++){
			if(s[i] == '0') c[0]++;
			if(s[i] == '1') c[1]++;
			if(s[i] == '?') c[2]++;
		}
		
		res = 0; p.clear();
		if(c[2] <= 6){
			in = 0;
			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) {
			t = 0, in = 0;
			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 if(c[1] <= 6) {
			t = 1, in = (1 << n) - 1;
			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];
			}
		} else assert(false);
		
		cout<<res<<"\n";
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25