Submission #1124429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124429		Muaath_5	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	602 ms	21724 KiB

snake_escaping

#include <bits/stdc++.h>
#pragma GCC target("popcnt")
#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];

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++) {
	  dp[0][i] = dp[1][i] = mask[i] = vals[i] - '0'; 
	}
	for (int i = 0; i < n; i++) {
		for (int msk = 0; msk < (1<<n); msk++) {
			if (msk & (1 << i))
				dp[0][msk] += dp[0][msk ^ (1 << i)];
			else
				dp[1][msk] += dp[1][msk ^ (1 << i)];
		}
		
	}
	
	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 += dp[x][init | msk];
			else
				ans -= dp[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: 53 / 53
• Subtask 5: 25 / 25