Submission #1290564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290564		duyanhchupapi	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	920 ms	17780 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = (1 << 20) + 200, infint = 2e9;
const ll infll = 9e18;
int q, L, dp[N], DP[N], mask0, mask1, cnt0, cnt1, cnt2, ans, sz;
string s;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	
	cin >> L >> q >> s;
	int base = (1 << L) - 1;
	for(int i = 0;i < (1 << L); ++i) DP[i] = s[i] - '0', dp[base ^ i] = DP[i];
	
	for(int j = 0; j < L; ++j) {
		for(int mask = 0; mask < (1 << L); ++mask) 
	 		if(mask & (1 << j)) 
			 	dp[mask ^ (1 << j)] += dp[mask], DP[mask ^ (1 << j)] += DP[mask];
	}

	while (q--) {
		string t;
		cin >> t;
		vector <int> luu0, luu1, luu2;
		ans = mask0 = mask1 = cnt0 = cnt1 = cnt2 = 0;
		
		for(int i = 0;i < L; ++i) {
			if(t[i] == '1') mask1 += (1 << L - i - 1), cnt1++, luu1.push_back(L - i - 1);
			else if(t[i] == '0') mask0 += (1 << L - i - 1), cnt0++, luu0.push_back(L - i - 1);
			else cnt2++, luu2.push_back(L - i - 1);
		}
		
		int kid = min({cnt0, cnt1, cnt2}), sz;
		if (cnt0 == kid) {
			sz = luu0.size();
			for(int mask = 0; mask < (1 << sz); ++mask) {
				int nmask = mask1, dem = 0;
				for (int i=0; i < sz; ++i) if(mask & (1 << i)) nmask |= (1 << luu0[i]), dem++;
				if(dem % 2 == 0) ans += DP[nmask];
				else ans -= DP[nmask];
			}
		}
		else if (cnt1 == kid) {
			sz = luu1.size();
			for(int mask = 0; mask < (1 << sz); ++mask) {
				int nmask = mask0, dem = 0;
				for (int i=0; i < sz; ++i) if(mask & (1 << i)) nmask |= (1 << luu1[i]), dem++;
				if(dem % 2 == 0) ans += dp[nmask];
				else ans -= dp[nmask];
			}
		}
		else {
			sz = luu2.size();
			for(int mask = 0; mask < (1 << sz); ++mask) {
				int nmask = mask1;
				for (int i = 0; i < sz; ++i) if(mask & (1 << i)) nmask |= (1 << luu2[i]);
				ans += s[nmask] - '0';
			}
		}
		
		cout << ans << '\n';
	}
	
	return 0;
}

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