Submission #958752

#	Time	Username	Problem	Language	Result	Execution time	Memory
958752		TAhmed33	Snake Escaping (JOI18_snake_escaping)	C++98	75 / 100	2001 ms	47608 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
const int B = 20;
int dp[2][1 << B], dq[2][1 << B], arr[1 << B];
int n, q;
int main () {
	cin >> n >> q;
	for (int i = 0; i < (1 << n); i++) {
		char s; cin >> s; int x = s - '0';
		arr[i] = x;
		dp[1][i] = dq[1][i] = x;
	}
	for (int i = 0, c = 0; i < n; i++, c ^= 1) {
		for (int j = 0; j < (1 << n); j++) {
			dp[c][j] = dp[c ^ 1][j];
			if (j & (1 << i)) dp[c][j] += dp[c ^ 1][j ^ (1 << i)];
			dq[c][j] = dq[c ^ 1][j];
			if (!(j & (1 << i))) dq[c][j] += dq[c ^ 1][j ^ (1 << i)];
		}
	}
	int ll = (n - 1) & 1;
	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) {
				assert(0 <= m && m < (1 << n));
				if (__builtin_popcount(m) & 1) {
					ret -= dq[ll][b | m];
				} else {
					ret += dq[ll][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[ll][c | m];
				} else {
					ret += dp[ll][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: 0 / 25