Submission #1124734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124734		beaboss	Snake Escaping (JOI18_snake_escaping)	C++20	12 / 100	2009 ms	25208 KiB

snake_escaping

// Source: https://oj.uz/problem/view/JOI18_snake_escaping
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }


const ll L = 20;

ll sub[1 << L];
ll super[1 << L], res[1 << L];



int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);


	ll n, l, q;
	cin >> l >> q;
	n = (1 << l);
	ll f = (1 << l) - 1;

	FOR(i, 0, n) {
		char c;
		cin >> c;
		sub[i] = c-'0';
		res[i] = c-'0';
		
		super[f ^ i] = c-'0';
	}

	FOR(suff, 0, l) {
		for (ll mask = n-1; mask >= 0; mask--) {
			ll cur = (mask >> suff);
			if (cur % 2 != 0) {
				sub[mask] += sub[mask - (1 << suff)];
				super[mask] += super[mask - (1 << suff)];
			}
		}
	}

	FOR(_, 0, q) {
		string s;
		cin >> s;

		vi a, b, c;
		reverse(s.begin(), s.end());

		for (ll i = l-1; i >= 0; i--) {
			if (s[i] == '0') b.pb(i);
			else if (s[i] == '1') a.pb(i);
			else c.pb(i);
		}

		if (a.size() <= 6) {

			ll ans = 0;

			ll begin = f;
			for (auto val: b) begin ^= (1 << val);

			// cout << begin << endl;
			FOR(mask, 0, (1 << a.size())) {
				ll cur = begin;
				ll flip = 1;
				FOR(j, 0, a.size()) {
					if ((1 << j) & mask) {
						flip*=-1;
						cur ^= (1 << a[j]);
					}
				}
				ans += flip * sub[cur];
			}
			cout << ans << endl;
		} else if (b.size() <= 6) {
			ll ans = 0;

			ll begin = f;
			for (auto val: a) begin ^= (1 << val);

			FOR(mask, 0, (1 << b.size())) {
				ll cur = begin;
				ll flip = 1;
				FOR(j, 0, b.size()) {
					if ((1 << j) & mask) {
						flip*=-1;
						cur ^= (1 << b[j]);
					}
				}
				ans += flip * super[cur];
			}
			cout << ans << endl;

		} else {
			assert(c.size() <= 6);
			
			ll ans = 0;
			FOR(mask, 0, c.size()) {
				ll cur = f;
				FOR(j, 0, c.size()) {
					if ((1 << j) & mask) cur ^= (1 << c[j]);
				}
				ans += res[cur];
			}

			cout << ans << endl;
		}
	}
}

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