Submission #1274322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274322		kaiboy	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	583 ms	22192 KiB

snake_escaping

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 20;

char aa[(1 << N) + 1], cc[N + 1];
int kk[1 << N], ss[1 << N], tt[1 << N];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q >> aa;
	for (int a = 0; a < 1 << n; a++)
		aa[a] -= '0';
	for (int a = 1; a < 1 << n; a++)
		kk[a] = kk[a & a - 1] + 1;
	for (int a = 0; a < 1 << n; a++) {
		ss[a] = aa[a ^ (1 << n) - 1];
		tt[a] = aa[a];
	}
	for (int i = 0; i < n; i++)
		for (int a = 0; a < 1 << n; a++)
			if (a >> i & 1) {
				ss[a ^ 1 << i] += ss[a];
				tt[a ^ 1 << i] += tt[a];
			}
	while (q--) {
		cin >> cc, reverse(cc, cc + n);
		int a = 0, b = 0, c = 0;
		for (int i = 0; i < n; i++)
			(cc[i] == '0' ? a : cc[i] == '1' ? b : c) ^= 1 << i;
		int s;
		if (kk[a] <= n / 3) {
			s = tt[b];
			for (int d = a; d; d = d - 1 & a)
				s += tt[b ^ d] * (kk[d] & 1 ? -1 : 1);
		} else if (kk[b] <= n / 3) {
			s = ss[a];
			for (int d = b; d; d = d - 1 & b)
				s += ss[a ^ d] * (kk[d] & 1 ? -1 : 1);
		} else {
			s = aa[b];
			for (int d = c; d; d = d - 1 & c)
				s += aa[b ^ d];
		}
		cout << s << '\n';
	}
	return 0;
}

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