Submission #1113380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113380		vjudge1	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	422 ms	65536 KiB

snake_escaping

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 20, SPLIT = 6;

int n, q, mask[1<<N];
string vals;

int dp[2][1<<N][N], sos[2][1<<N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> q >> vals;
	for (int i = 0; i < (1<<n); i++)
		mask[i] = vals[i] - '0';
	for (int i = 0; i <= n; i++) {
		for (int msk = 0; msk < (1<<n); msk++) {
			if(!i){
				dp[0][msk][0] = mask[msk];
				// if(msk % 2) dp[0][msk][0] += mask[msk - 1];
				dp[1][msk][0] = mask[msk];
				// if(msk % 2 == 0) dp[1][msk][0] += mask[msk + 1];
				continue;
			}
			dp[0][msk][i] += dp[0][msk][i-1];
			dp[1][msk][i] += dp[1][msk][i-1];
			if (msk & (1 << (i-1)))
				dp[0][msk][i] += dp[0][msk ^ (1 << (i-1))][i-1];
			else
				dp[1][msk][i] += dp[1][msk ^ (1 << (i-1))][i-1];
			sos[0][msk] = dp[0][msk][n];
			sos[1][msk] = dp[1][msk][n];
		}
		
	}
	
	while (q--) {
		string b;
		cin >> b;
		int c_marks=0, cc[2]={};
		for (char c : b)
			if (c == '?')
				c_marks++;
			else
				cc[c-'0']++;
		
		
		if (c_marks <= SPLIT) {
			int init = 0;
			int marks = 0;
			for (int i = 0; i < n; i++)
				if (b[i] == '1')
					init |= (1 << (n-i-1));
				else if (b[i] == '?')
					marks |= (1 << (n-i-1));
			
			int ans = 0;
			for (int msk = marks; msk >= 0; msk = (msk-1)&marks) {
				ans += mask[init | msk];	
				if (msk == 0) break;
			}
			cout << ans << '\n';
			continue;
		}
		
		int x = (cc[1] <= SPLIT ? 0 : 1);
		
		int init = 0;
		int marks = 0;
		for (int i = 0; i < n; i++) {	
			if (b[i] == '?' && x == 0)
				init |= (1 << (n-i-1));
			
			if (b[i] == '1' && x == 1)
				init |= (1 << (n-i-1));
				
			if (x == 0 && b[i] == '1')
				marks |= (1 << (n-i-1));
				
			if (x == 1 && b[i] == '0')
				marks |= (1 << (n-i-1));
		}
			
		int ans = 0;
		for (int msk = marks; msk >= 0; msk = (msk-1)&marks) {
			if (__builtin_popcount(msk)%2 == cc[x] % 2)
				ans += sos[x][init | msk];
			else
				ans -= sos[x][init | msk];
			if (msk == 0) break;
		}
		
		cout << abs(ans) << '\n';
	}
}

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