Submission #604251

#	Time	Username	Problem	Language	Result	Execution time	Memory
604251		Asymmetry	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1160 ms	42168 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int L, Q;
	cin >> L >> Q;
	vector<int> t(1 << L);
	for (int &i : t) {
		char c;
		cin >> c;
		i = c - '0';
	}
	auto r = t;
	REP (i, 1 << L) {
		if (i < (i ^ ((1 << L) - 1))) {
			swap(r[i], r[i ^ ((1 << L) - 1)]);
		}
	}

	auto SOS = [&](vector<int> &v) {
		REP (i, L) {
			REP (j, 1 << L) {
				if (j & (1 << i)) {
					v[j] += v[j ^ (1 << i)];
				}
			}
		}
	};
	
	auto v = t;
	SOS(v);
	SOS(r);
	
	map<char, int> mp;
	mp['0'] = 0;
	mp['1'] = 1;
	mp['?'] = 2;
	REP (i, Q) {
		vector<char> w(L);
		vector<int> z(3);
		for (char &j : w) {
			cin >> j;
			++z[mp[j]];
		}
		reverse(w.begin(), w.end());
		if (z[0] <= z[1] && z[0] <= z[2]) {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					bas ^= 1 << j;
				}
				else if (w[j] == '0') {
					msk ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				if (__builtin_parity(msk ^ j)) {
					odp -= r[j ^ bas];
				}
				else {
					odp += r[j ^ bas];
				}
			}
			cout << odp + (__builtin_parity(msk) ? -r[bas] : r[bas]) << '\n';
		}
		else if (z[1] <= z[0] && z[1] <= z[2]) {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					bas ^= 1 << j;
				}
				else if (w[j] == '1') {
					msk ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				if (__builtin_parity(msk ^ j)) {
					odp -= v[j ^ bas];
				}
				else {
					odp += v[j ^ bas];
				}
			}
			cout << odp + (__builtin_parity(msk) ? -v[bas] : v[bas]) << '\n';
		}
		else {
			int odp = 0, bas = 0, msk = 0;
			REP (j, L) {
				if (w[j] == '?') {
					msk ^= 1 << j;
				}
				else if (w[j] == '1') {
					bas ^= 1 << j;
				}
			}
			for (int j = msk; j; j = (j - 1) & msk) {
				odp += t[bas ^ j];
			}
			cout << odp + t[bas] << '\n';
		}
	}
}

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