Submission #940768

#	Time	Username	Problem	Language	Result	Execution time	Memory
940768		lorenzoferrari	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	750 ms	42212 KiB

snake_escaping

#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static int constexpr L = 20;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int l; cin >> l;
	int q; cin >> q;
	auto neg = [&](int mask) -> int {
		return ~mask & ((1 << l) - 1);
	};
	static int s[1 << L]{};
	for (int i = 0; i < (1 << l); ++i) {
		char c; cin >> c;
		s[i] = c - '0';
	}

	static int sos[2][1 << L]{};
	for (int i = 0; i < (1 << l); ++i) {
		sos[0][i] += s[i];
		sos[1][neg(i)] += s[i];
	}
	for (int i = 0; i < l; ++i) {
		for (int mask = 0; mask < (1 << l); ++mask) {
			if (mask & (1 << i)) {
				sos[0][mask] += sos[0][mask ^ (1 << i)];
			}
		}
	}
	for (int i = 0; i < l; ++i) {
		for (int mask = 0; mask < (1 << l); ++mask) {
			if (mask & (1 << i)) {
				sos[1][mask] += sos[1][mask ^ (1 << i)];
			}
		}
	}

	for (int i = 0; i < q; ++i) {
		string t; cin >> t;
		int zeros = 0, ones = 0, marks = 0;
		for (int j = 0; j < l; ++j) {
			if (t[j] == '0') zeros|= (1 << (l - 1 - j));
			if (t[j] == '1') ones |= (1 << (l - 1 - j));
			if (t[j] == '?') marks|= (1 << (l - 1 - j));
		}
		int c0 = __builtin_popcount(zeros);
		int c1 = __builtin_popcount(ones);
		int cm = __builtin_popcount(marks);
		int ans = 0;
		if (cm <= c0 && cm <= c1) {
			ans = s[ones];
			for (int mask = marks; mask > 0; mask = (mask - 1) & marks) {
				ans += s[ones | mask];
			}
		} else if (c1 <= c0 && c1 <= cm) {
			ans = sos[0][ones | marks];
			for (int diff = ones; diff > 0; diff = (diff - 1) & ones) {
				if (__builtin_popcount(diff) & 1) {
					ans -= sos[0][(ones ^ diff) | marks];
				} else {
					ans += sos[0][(ones ^ diff) | marks];
				}
			}
		} else {
			ans = sos[1][zeros | marks];
			for (int diff = zeros; diff > 0; diff = (diff - 1) & zeros) {
				if (__builtin_popcount(diff) & 1) {
					ans -= sos[1][(zeros ^ diff) | marks];
				} else {
					ans += sos[1][(zeros ^ diff) | marks];
				}
			}
		}
		cout << ans << "\n";
	}
}

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