Submission #1283147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283147		euthymia2606	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	464 ms	20812 KiB

snake_escaping

#include <bits/stdc++.h> 

using namespace std;  

typedef long long ll;  
typedef pair<int, int> ii;  

const int INF = 1e9;  
const ll LINF = 1e18;  

int L, q;  
int toxic[1 << 20]; 

int sos_sub[1 << 20], sos_super[1 << 20];

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> L >> q; 
	for (int i = 0; i < (1 << L); i++) {
		char c; cin >> c; 
		toxic[i] = c - '0'; 
	}	

	for (int mask = 0; mask < (1 << L); mask++) {
		sos_sub[mask] = sos_super[mask] = toxic[mask];
	}

	for (int i = 0; i < L; i++) {
		for (int mask = 0; mask < (1 << L); mask++) {
			if (mask & (1 << i)) sos_sub[mask] += sos_sub[mask ^ (1 << i)];
			else sos_super[mask] += sos_super[mask ^ (1 << i)];
		}
	}

	while (q--) {
		string t; cin >> t; 
		reverse(t.begin(), t.end());  

		int mask_z = 0, mask_o = 0, mask_q = 0;  
		for (int i = 0; i < L; i++) {
			if (t[i] == '0') mask_z |= (1 << i);  
			if (t[i] == '1') mask_o |= (1 << i);  
			if (t[i] == '?') mask_q |= (1 << i);
		}

		int ans = 0; 
		if (__builtin_popcount(mask_q) <= 6) {
			ans = toxic[mask_o];   
			for (int sub = mask_q; sub > 0; sub = (sub - 1) & mask_q) {
				ans += toxic[sub | mask_o];
			}
		}
		else if (__builtin_popcount(mask_o) <= 6) {
			ans = (__builtin_parity(mask_o) ? -1 : 1) * sos_sub[mask_q];
			for (int sub = mask_o; sub > 0; sub = (sub - 1) & mask_o) {
				int sign = __builtin_parity(sub) ^ __builtin_parity(mask_o) ? -1 : 1;
				ans += sign * sos_sub[sub | mask_q];
			}
		}
		else {
			ans = sos_super[mask_o]; 
			for (int sub = mask_z; sub > 0; sub = (sub - 1) & mask_z) {
				int sign = __builtin_parity(sub) ? -1 : 1;
				ans += sign * sos_super[sub | mask_o];
			}
		}

		cout << ans << '\n';
	}
}

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