Submission #958755

#	Time	Username	Problem	Language	Result	Execution time	Memory
958755		TAhmed33	Snake Escaping (JOI18_snake_escaping)	C++98	100 / 100	543 ms	42088 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("popcnt")
const int B = 20;
int dp[1 << B], dq[1 << B], arr[1 << B];
int n, q;
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int i = 0; i < (1 << n); i++) {
		char s; cin >> s; int x = s - '0';
		arr[i] = dp[i] = dq[i] = x;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < (1 << n); j++) {
			if (!(j & (1 << i))) dq[j] += dq[j ^ (1 << i)];
		}
		for (int j = (1 << n) - 1; j >= 0; j--) {
			if (j & (1 << i)) dp[j] += dp[j ^ (1 << i)];
		}
	}
	while (q--) {
		string s; cin >> s;
		int a = 0, b = 0, c = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == '0') {
				a ^= 1 << (n - i - 1);
			} else if (s[i] == '1') {
				b ^= 1 << (n - i - 1);
			} else {
				c ^= 1 << (n - i - 1);
			}
		}
		int ret = 0;
		if (__builtin_popcount(a) <= 6) {
			int m = a;
			while (true) {
				if (__builtin_popcount(m) & 1) {
					ret -= dq[b | m];
				} else {
					ret += dq[b | m];
				}
				if (m == 0) break;
				m = (m - 1) & a;
			}
		} else if (__builtin_popcount(b) <= 6) {
			int m = b;
			while (true) {
				if (__builtin_popcount(m) & 1) {
					ret -= dp[c | m];
				} else {
					ret += dp[c | m];
				}
				if (m == 0) break;
				m = (m - 1) & b;
			} 
		} else {
			int m = c;
			while (true) {
				ret += arr[b ^ m];
				if (m == 0) break;
				m = (m - 1) & c;
			} 
		}
		cout << (ret < 0 ? -ret : ret) << '\n';
	}
}

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