Submission #1274278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274278		kaiboy	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	1436 ms	72396 KiB

snake_escaping

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 20;
const int Q = 1000000;
const int M = 6;
const int P = 4782969;

char aa[(1 << N) + 1], cc[Q][N + 1];
int pp[N], bb[Q], ans[Q], ii[P], ss[P];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q >> aa;
	int m = min(M, n), p_ = 1;
	for (int i = m; i < n; i++)
		pp[i] = p_, p_ *= 3;
	for (int h = 0; h < q; h++) {
		cin >> cc[h], reverse(cc[h], cc[h] + n);
		for (int i = m; i < n; i++)
			bb[h] += (cc[h][i] != '?' ? cc[h][i] - '0' : 2) * pp[i];
	}
	for (int b = 0; b < p_; b++) {
		int i = m;
		while (i < n && b / pp[i] % 3 != 2)
			i++;
		if (i < n) {
			ii[b] = i;
			continue;
		}
		int a = 0;
		for (i = m; i < n; i++)
			a ^= b / pp[i] % 3 << i;
		ii[b] = -a;
	}
	for (int a = 0; a < 1 << m; a++) {
		for (int b = 0; b < p_; b++) {
			int i = ii[b];
			ss[b] = i > 0 ? ss[b - pp[i] * 2] + ss[b - pp[i]] : aa[-i ^ a] - '0';
		}
		for (int h = 0; h < q; h++) {
			bool yes = true;
			for (int i = 0; i < m; i++)
				if (cc[h][i] != '?' && cc[h][i] - '0' != (a >> i & 1)) {
					yes = false;
					break;
				}
			if (yes)
				ans[h] += ss[bb[h]];
		}
	}
	for (int h = 0; h < q; h++)
		cout << ans[h] << '\n';
	return 0;
}

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