제출 #1274274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274274		kaiboy	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2093 ms	48780 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 bb[Q], ss[P], ans[Q];

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++)
		p_ *= 3;
	for (int h = 0; h < q; h++) {
		cin >> cc[h], reverse(cc[h], cc[h] + n);
		for (int i = n - 1; i >= m; i--)
			bb[h] = bb[h] * 3 + (cc[h][i] != '?' ? cc[h][i] - '0' : 2);
	}
	for (int a = 0; a < 1 << m; a++) {
		for (int b = 0; b < p_; b++) {
			int i = m, p = 1;
			while (i < n && b / p % 3 != 2)
				i++, p *= 3;
			if (i == n) {
				int a_ = a;
				for (i = m, p = 1; i < n; i++, p *= 3)
					a_ ^= b / p % 3 << i;
				ss[b] = aa[a_] - '0';
			} else
				ss[b] = ss[b - p * 2] + ss[b - p];
		}
		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