Submission #705581

#	Time	Username	Problem	Language	Result	Execution time	Memory
705581		rainboy	Snake Escaping (JOI18_snake_escaping)	C11	100 / 100	1912 ms	28372 KiB

snake_escaping

#include <stdio.h>

#define N	20
#define M	12
#define L	8
#define Q	1000000
#define N_	531441

int min(int a, int b) { return a < b ? a : b; }

int pp3[M + 1];

void init() {
	int m;

	pp3[0] = 1;
	for (m = 1; m <= M; m++)
		pp3[m] = pp3[m - 1] * 3;
}

void solve(char *cc, int *dp, int m) {
	int p, i;

	if (m == 0) {
		dp[0] = cc[0] - '0';
		return;
	}
	p = pp3[m - 1];
	solve(cc, dp, m - 1);
	solve(cc + (1 << m - 1), dp + p, m - 1);
	for (i = 0; i < p; i++)
		dp[p * 2 + i] = dp[i] + dp[p + i];
}

int main() {
	static char cc[(1 << N) + 1];
	static int bb_[Q], lower[Q], upper[Q], ans[Q], dp[N_];
	int n, m, l, q, h, i, b;

	init();
	scanf("%d%d%s", &n, &q, cc), m = min(n, M), l = n - m;
	for (h = 0; h < q; h++) {
		static char s[N + 1];

		scanf("%s", s);
		for (i = m - 1; i >= 0; i--)
			bb_[h] = bb_[h] * 3 + (s[n - 1 - i] == '?' ? 2 : (s[n - 1 - i] == '0' ? 0 : 1));
		for (i = 0; i < l; i++)
			if (s[n - 1 - m - i] == '1')
				lower[h] |= 1 << i, upper[h] |= 1 << i;
			else if (s[n - 1 - m - i] == '?')
				upper[h] |= 1 << i;
	}
	for (b = 0; b < 1 << l; b++) {
		solve(cc + (b << m), dp, m);
		for (h = 0; h < q; h++)
			if ((lower[h] & b) == lower[h] && (upper[h] | b) == upper[h])
				ans[h] += dp[bb_[h]];
	}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

snake_escaping.c: In function 'solve':
snake_escaping.c:30:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   30 |  solve(cc + (1 << m - 1), dp + p, m - 1);
      |                   ~~^~~
snake_escaping.c: In function 'main':
snake_escaping.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d%s", &n, &q, cc), m = min(n, M), l = n - m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~

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