제출 #535339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535339		amunduzbaev	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1473 ms	42232 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int N = 20;
int dp[2][1 << N];
int a[1 << N], n, m;

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

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