Submission #848699

#	Time	Username	Problem	Language	Result	Execution time	Memory
848699		TranGiaHuy1508	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	871 ms	38680 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

const int maxn = 1 << 20;

int lg, n, q;
vector<int> v;

vector<int> subsetZeta(vector<int> V){
	for (int j = 0; j < lg; j++){
		for (int i = 0; i < n; i++){
			if (((i >> j) & 1)){
				V[i] += V[i ^ (1 << j)];
			}
		}
	}
	return V;
}

vector<int> supersetZeta(vector<int> V){
	for (int j = 0; j < lg; j++){
		for (int i = 0; i < n; i++){
			if (((i >> j) & 1) == 0){
				V[i] += V[i ^ (1 << j)];
			}
		}
	}
	return V;
}

void main_program(){
	cin >> lg >> q;
	n = 1 << lg;

	v.resize(n);
	string s; cin >> s;
	for (int i = 0; i < n; i++) v[i] = (s[i] - '0');

	vector<int> subset = subsetZeta(v), superset = supersetZeta(v);

	for (int _ = 0; _ < q; _++){
		string Q; cin >> Q;

		int mask0 = 0, mask1 = 0, mask2 = 0;
		for (int i = 0; i < lg; i++){
			if (Q[i] == '0') mask0 |= (1 << (lg-1 - i));
			if (Q[i] == '1') mask1 |= (1 << (lg-1 - i));
			if (Q[i] == '?') mask2 |= (1 << (lg-1 - i));
		}
		int popcnt0 = __builtin_popcount(mask0);
		int popcnt1 = __builtin_popcount(mask1);
		int popcnt2 = __builtin_popcount(mask2);
		int mn = min({popcnt0, popcnt1, popcnt2});

		if (popcnt0 == mn){
			int sum = 0;
			for (int submask = mask0; submask > 0; submask = (submask - 1) & mask0){
				int num = mask1 + submask;
				int sign = ((__builtin_popcount(submask) & 1)) ? -1 : 1;
				sum += superset[num] * sign;
			}
			{
				int submask = 0;
				int num = mask1 + submask;
				int sign = ((__builtin_popcount(submask) & 1)) ? -1 : 1;
				sum += superset[num] * sign;
			}
			cout << sum << "\n";
		}
		else if (popcnt1 == mn){
			int sum = 0;
			for (int submask = mask1; submask > 0; submask = (submask - 1) & mask1){
				int num = mask2 + submask;
				int sign = ((__builtin_popcount(submask) & 1) == (popcnt1 & 1)) ? 1 : -1;
				sum += subset[num] * sign;
			}
			{
				int submask = 0;
				int num = mask2 + submask;
				int sign = ((__builtin_popcount(submask) & 1) == (popcnt1 & 1)) ? 1 : -1;
				sum += subset[num] * sign;
			}
			cout << sum << "\n";
		}
		else{
			int sum = 0;
			for (int submask = mask2; submask > 0; submask = (submask - 1) & mask2){
				int num = mask1 + submask;
				sum += v[num];
			}
			{
				int submask = 0;
				int num = mask1 + submask;
				sum += v[num];
			}
			cout << sum << "\n";
		}
	}
}

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