제출 #1168682

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168682		xnqs	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1409 ms	17828 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(const 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;

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

		// min_cnt <= 6
		int min_cnt = std::min({aps[0].size(), aps[1].size(), aps[2].size()});
		if (aps[2].size() == min_cnt) {
			int ret = 0;
			for (int mask = 0; mask < (1<<aps[2].size()); mask++) {
				for (int i = 0; i < aps[2].size(); i++) {
					pattern[aps[2][i]] = ((mask>>i)&1) + '0';
				}
				ret += str[to_decimal(pattern)]-'0';
			}

			std::cout << ret << "\n";
		}
		else if (aps[0].size() == min_cnt) {
			int ret = 0;
			int one_mask = 0;
			for (int i = 0; i < aps[1].size(); i++) {
				one_mask |= (1<<(x-aps[1][i]-1));
			}

			for (int mask = 0; mask < (1<<aps[0].size()); mask++) {
				int full_mask = one_mask;
				for (int i = 0; i < aps[0].size(); i++) {
					if (mask&(1<<i)) {
						full_mask |= (1<<(x-aps[0][i]-1));
					}
				}
				int sgn = ((__builtin_popcount(mask))&1) ? -1 : 1;
				ret += sgn * dp_supersets[full_mask];
			}

			std::cout << ret << "\n";
		}
		else {
			int ret = 0;
			int question_mask = 0;
			for (int i = 0; i < aps[2].size(); i++) {
				question_mask |= (1<<(x-aps[2][i]-1));
			}

			for (int mask = 0; mask < (1<<aps[1].size()); mask++) {
				int full_mask = question_mask;
				for (int i = 0; i < aps[1].size(); i++) {
					if (mask&(1<<i)) {
						full_mask |= (1<<(x-aps[1][i]-1));
					}
				}

				int sgn = ((aps[1].size()-__builtin_popcount(mask))&1) ? -1 : 1;
				ret += sgn * dp_subsets[full_mask];
			}

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

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