Submission #1124740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124740		beaboss	Snake Escaping (JOI18_snake_escaping)	C++20	22 / 100	770 ms	12872 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<int, int> pii;
typedef vector<pii> vpii;

typedef vector<int> vi;

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

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

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


const int L = 20;

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



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


	int n, l, q;
	cin >> l >> q;
	n = (1 << l);
	int 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 (int mask = n-1; mask >= 0; mask--) {
			int 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 (int 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) {

			int ans = 0;

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

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

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

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

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

			cout << ans;
		}

		cout << '\n';
	}
}

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