Submission #696226

#	Time	Username	Problem	Language	Result	Execution time	Memory
696226		rainboy	Solitaire (JOI16_solitaire)	C11	100 / 100	57 ms	448 KiB

solitaire

#include <stdio.h>

#define N	2000
#define M	(N * 3)
#define MD	1000000007

int main() {
	static char cc[3][N + 1];
	static int dp[M + 1][2], dq[M + 1][2];
	int n, m, k, h, i, j, x, ans;

	scanf("%d", &n);
	for (h = 0; h < 3; h++)
		scanf("%s", cc[h]);
	if (cc[0][0] == 'x' || cc[2][0] == 'x' || cc[0][n - 1] == 'x' || cc[2][n - 1] == 'x') {
		printf("0\n");
		return 0;
	}
	for (i = 1; i < n; i++)
		if (cc[0][i] == 'x' && cc[0][i - 1] == 'x' || cc[2][i] == 'x' && cc[2][i - 1] == 'x') {
			printf("0\n");
			return 0;
		}
	m = 0;
	dp[0][0] = 1;
	for (i = 0; i < n; i++) {
		k = 0;
		if (cc[0][i] == 'x')
			k++;
		if (cc[2][i] == 'x')
			k++;
		if (cc[1][i] == 'o') {
			for (j = 0; j <= m; j++)
				dq[j][0] = dq[j][1] = 0;
			if (k == 0)
				x = 1;
			else if (k == 1)
				x = m + 1;
			else
				x = (m + 1) * (m + 2);
			for (j = 0; j <= m; j++) {
				dq[0][0] = (dq[0][0] + (long long) dp[j][0] * x) % MD;
				dq[0][0] = (dq[0][0] + (long long) dp[j][1] * x) % MD;
			}
			for (j = 0; j <= m + k; j++)
				dp[j][0] = dq[j][0], dp[j][1] = dq[j][1];
			m += k;
		} else {
			for (j = 0; j <= m + 1; j++)
				dq[j][0] = dq[j][1] = 0;
			x = 0;
			for (j = 0; j <= m; j++) {
				x = (x + dp[j][0]) % MD;
				dq[j + 1][1] = (dq[j + 1][1] + x) % MD;
			}
			for (j = 1; j <= m + 1; j++)
				dq[j][0] = (dq[j][0] + x) % MD;
			x = 0;
			for (j = m; j >= 0; j--) {
				x = (x + dp[j][1]) % MD;
				if (j > 0)
					dq[j][0] = (dq[j][0] + x) % MD;
			}
			for (j = 0; j <= m + 1; j++)
				dp[j][0] = dq[j][0], dp[j][1] = dq[j][1];
			m++;
			for (j = 0; j <= m + k; j++)
				dq[j][0] = dq[j][1] = 0;
			if (k == 0) {
				for (j = 1; j <= m; j++) {
					x = dp[j][0];
					dq[j][0] = (dq[j][0] + x) % MD;
				}
			} else if (k == 1) {
				for (j = 1; j <= m; j++) {
					x = dp[j][0];
					dq[j + 1][0] = (dq[j + 1][0] + (long long) x * j) % MD;
					x = dp[j][1];
					dq[j][1] = (dq[j][1] + (long long) x * (m - j + 1)) % MD;
				}
			} else {
				for (j = 1; j <= m; j++) {
					x = dp[j][0];
					dq[j + 2][0] = (dq[j + 2][0] + (long long) x * j * (j + 1)) % MD;
					x = dp[j][1];
					dq[j][1] = (dq[j][1] + (long long) x * (m - j + 1) * (m - j + 2)) % MD;
					dq[j + 1][1] = (dq[j + 1][1] + (long long) x * j * (m - j + 1) * 2) % MD;
				}
			}
			for (j = 0; j <= m + k; j++)
				dp[j][0] = dq[j][0], dp[j][1] = dq[j][1];
			m += k;
		}
	}
	ans = 0;
	for (j = 0; j <= m; j++) {
		ans = (ans + dp[j][0]) % MD;
		ans = (ans + dp[j][1]) % MD;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

solitaire.c: In function 'main':
solitaire.c:20:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |   if (cc[0][i] == 'x' && cc[0][i - 1] == 'x' || cc[2][i] == 'x' && cc[2][i - 1] == 'x') {
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
solitaire.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
solitaire.c:14:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%s", cc[h]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 20 / 20
• Subtask 4: 38 / 38
• Subtask 5: 20 / 20