Submission #1144730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144730		thecrazycandy	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1516 ms	43400 KiB

snake_escaping

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)(1 << 21);
char a[MAXN];
ll dp1[MAXN];
ll dp[MAXN];
int main () {
	sped_up;
	ll n, k;
	cin >> n >> k;
	for (int mask = 0; mask < (1 << n); mask++) {
		cin >> a[mask];
		dp[mask] += a[mask] - '0';
		dp1[mask] += a[mask] - '0';
	}
	for (int i = 0; i < n; i++) {
		for (int mask = 0; mask < (1 << n); mask++) {
			if (((mask >> i) & 1) == 1) dp[mask] += dp[mask ^ (1 << i)];
		}
		for (int mask = (1 << n) - 1; mask >= 0; mask--) {
			if (((mask >> i) & 1) == 0) dp1[mask] += dp1[mask ^ (1 << i)];
		}
	}
	while (k--) {
		char c[n];
		vector <ll> o, z, q;
		ll cnt = 0, sum = 0;
		ll msk = 0, msk1 = 0, msk2 = 0;
		for (int i = n - 1; i >= 0; i--) {
			cin >> c[i];
			if (c[i] == '1') msk |= (1 << i), o.push_back(i);
			else if (c[i] == '?') msk1 |= (1 << i), q.push_back(i);
			else msk2 |= (1 << i), z.push_back(i);
		}
		if (o.size() <= 6) {
			for (int mask = 0; mask < (1 << o.size()); mask++) {
				ll rmask = 0;
				for (int i = 0; i < o.size(); i++) {
					if (((mask >> i) & 1) == 1) rmask |= (1 << o[i]);
				}
				if (__builtin_popcount(mask) % 2 == 0) sum += dp[(msk | msk1) ^ rmask];
				else sum -= dp[(msk | msk1) ^ rmask];
			}
		}
		else if (q.size() <= 6) {
			for (int mask = 0; mask < (1 << q.size()); mask++) {
				ll rmask = 0;
				for (int i = 0; i < q.size(); i++) {
					if (((mask >> i) & 1) == 1) rmask |= (1 << q[i]);
				}
				sum += a[msk | rmask] - '0';
			}
		}
		else {
			for (int mask = 0; mask < (1 << z.size()); mask++) {
				ll rmask = 0;
				for (int i = 0; i < z.size(); i++) {
					if (((mask >> i) & 1) == 1) rmask |= (1 << z[i]);
				}
				if (__builtin_popcount(mask) % 2 == 0) sum += dp1[msk | rmask];
				else sum -= dp1[msk | rmask];
			}
		}
		cout << sum << '\n';
	}
}

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