Submission #1168678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168678		xnqs	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2093 ms	18036 KiB

snake_escaping

#pragma GCC optimize("Ofast")

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>

int x, q;
std::string str;
int dp_subsets[1<<20];
int dp_supersets[1<<20];

void precalc_dp() {
	for (int i = 0; i < (1<<x); i++) {
		dp_subsets[i] = str[i] - '0';
	}
	for (int i = 0; i < x; i++) {
		for (int mask = 0; mask < (1<<x); mask++) {
			if (mask&(1<<i)) {
				dp_subsets[mask] += dp_subsets[mask^(1<<i)];
			}
		}
	}

	for (int i = 0; i < (1<<x); i++) {
		dp_supersets[i] = str[i] - '0';
	}
	for (int i = 0; i < x; i++) {
		for (int mask = (1<<x)-1; mask >= 0; mask--) {
			if (!(mask&(1<<i))) {
				dp_supersets[mask] += dp_supersets[mask^(1<<i)];
			}
		}
	}
}

int to_decimal(std::string str) {
	int ret = 0;
	for (int i = 0; i < str.size(); i++) {
		ret <<= 1;
		ret += (str[i]=='1');
	}
	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> q;
	std::cin >> str;

	precalc_dp();
	/*for (int i = 0; i < (1<<x); i++) {
		std::cout << i << " " << dp_subsets[i] << " " << dp_supersets[i] << "\n";
	}*/
	while (q--) {
		std::string pattern;
		std::cin >> pattern;

		int aps[3] = {0};
		aps[0] = aps[1] = aps[2] = 0;
		for (int i = 0; i < x; i++) {
			if (pattern[i] == '0' || pattern[i] == '1') {
				aps[pattern[i]-'0'] |= (1<<(x-i-1));
			}
			else {
				aps[2] |= (1<<(x-i-1));
			}
		}

		// min_cnt <= 6
		int min_cnt = std::min({
				__builtin_popcount(aps[0]),
				__builtin_popcount(aps[1]),
				__builtin_popcount(aps[2])});
		if (__builtin_popcount(aps[2]) == min_cnt) {
			int ret = 0;
			for (int mask = aps[2]; mask >= 0; mask = (mask-1)&aps[2]) {
				for (int i = 0; i < x; i++) {
					if (!(aps[2]&(1<<i))) {
						continue;
					}
					if (mask&(1<<i)) {
						pattern[x-i-1] = '1';
					}
					else {
						pattern[x-i-1] = '0';
					}
				}

				ret += str[to_decimal(pattern)]-'0';

				if (!mask) {
					break;
				}
			}

			std::cout << ret << "\n";
		}
		else if (__builtin_popcount(aps[0]) == min_cnt) {
			int ret = 0;
			int one_mask = aps[1];

			for (int mask = aps[0]; mask >= 0; mask = (mask-1)&aps[0]) {
				int sgn = ((__builtin_popcount(mask))&1) ? -1 : 1;
				int full_mask = mask | aps[1];
				ret += sgn * dp_supersets[full_mask];

				if (!mask) {
					break;
				}
			}

			std::cout << ret << "\n";
		}
		else {
			int ret = 0;
			int question_mask = aps[2];

			for (int mask = aps[1]; mask >= 0; mask = (mask-1)&aps[1]) {
				int sgn = ((__builtin_popcount(aps[1])-__builtin_popcount(mask))&1) ? -1 : 1;
				int full_mask = aps[2] | mask;
				ret += sgn * dp_subsets[full_mask];

				if (!mask) {
					break;
				}
			}

			std::cout << ret << "\n";
		}
	}
}

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