제출 #1274279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274279		kaiboy	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1879 ms	60788 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], tt[N + 1], cc[Q][M];
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 >> tt, reverse(tt, tt + n);
		for (int i = 0; i < n; i++)
			if (i < m)
				cc[h][i] = tt[i];
			else
				bb[h] += (tt[i] != '?' ? tt[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: 25 / 25