Submission #535670

#	Time	Username	Problem	Language	Result	Execution time	Memory
535670		iliaM	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1657 ms	24648 KiB

snake_escaping

#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "

constexpr int N = (1 << 20) + 10;

int a[N], f[N], g[N], h[N];
int n, m;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 0; i < (1 << n); ++i) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	
	int comp = (1 << n) - 1;
	for (int i = 0; i < (1 << n); ++i) {
		f[i] = g[i ^ comp] = a[i];
	}
	for (int i = 0; i < n; ++i) {
		for (int mask = 0; mask < (1 << n); ++mask) {
			if ((mask >> i) & 1) {
				f[mask] += f[mask ^ (1 << i)];
				g[mask] += g[mask ^ (1 << i)];
			}
		}
	}
	for (int i = 0; i < (1 << n); ++i) {
		h[i] = g[i ^ comp];
	}
	
	while (m--) {
		string s;
		cin >> s;
		int cnt0 = 0, cnt1 = 0, num = 0, numm = 0;
		reverse(s.begin(), s.end());
		vector<int> idx[3];
		fill(idx, idx + 3, vector<int>());
		for (int i = 0; i < n; ++i) {
			cnt0 += s[i] == '0';
			cnt1 += s[i] == '1';
			if (s[i] == '1') {
				idx[1].push_back(i);
				num += (1 << i);
				numm += (1 << i);
			}
			if (s[i] == '?') {
				idx[2].push_back(i);
				numm += (1 << i);
			}
			if (s[i] == '0') {
				idx[0].push_back(i);
			}
		}

		int sum = 0;
		if (cnt1 <= 6) {
			for (int mask = 0; mask < (1 << cnt1); ++mask) {
				int num2 = numm;
				for (int i = 0; i < (int) idx[1].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[1][i];
				}
				sum += (__builtin_parity(mask) ? -1 : +1) * f[num2];
			}
		} else if (n - cnt0 - cnt1 <= 6) {
			int cnt = n - cnt0 - cnt1;
			for (int mask = 0; mask < (1 << cnt); ++mask) {
				int num2 = num;
				for (int i = 0; i < (int) idx[2].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[2][i];
				}
				sum += a[num2];
			}
		} else {
			for (int mask = 0; mask < (1 << cnt0); ++mask) {
				int num2 = num;
				for (int i = 0; i < (int) idx[0].size(); ++i) {
					num2 ^= ((mask >> i) & 1) << idx[0][i];
				}
				sum += (__builtin_parity(mask) ? -1 : +1) * h[num2];
			}
		}
		cout << sum << '\n';
	}
}

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