Submission #53278

#	Time	Username	Problem	Language	Result	Execution time	Memory
53278		ainta	Solitaire (JOI16_solitaire)	C++17	100 / 100	371 ms	1688 KiB

solitaire

#include<cstdio>
#include<algorithm>
using namespace std;
int n, w[2010][5], C[2010];
int cnt;
long long D[6010][2], dd, Mod = 1000000007, TD[6010][2];
char q[2010];
int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= 3; i++) {
		scanf("%s", q + 1);
		for (j = 1; j <= n; j++) {
			if (q[j] == 'o')w[j][i] = 1;
		}
	}
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= 3; j++) {
			if (w[i][j] + w[i + 1][j] + w[i][j + 1] + w[i + 1][j + 1] == 0) {
				puts("0");
				return 0;
			}
		}
	}
	dd = 1;
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= 3; j++)if (!w[i][j])C[i] += (1 << (j - 1));
	}
	for (i = 1; i <= n; i++) {
		if (!(C[i-1]&2)) {
			if (C[i] == 7) {
				cnt += 3;
				for (j = 1; j <= cnt; j++) {
					int c1 = (j - 1)*(j - 2);
					int c2 = (cnt - 1)*(cnt - 2) - c1;
					D[j][0] = dd*c1 % Mod;
					D[j][1] = dd*c2 % Mod;
				}
			}
			if (C[i] == 5) {
				cnt += 2;
				dd = cnt*(cnt - 1)*dd%Mod;
			}
			if (C[i] == 1 || C[i] == 4) {
				cnt++;
				dd = dd*cnt%Mod;
			}
			if (C[i] == 3 || C[i] == 6) {
				cnt+=2;
				for (j = 1; j <= cnt; j++) {
					D[j][0] = dd*(j - 1) % Mod;
					D[j][1] = dd*(cnt - j) % Mod;
				}
			}
			if (C[i] == 2) {
				cnt++;
				for (j = 1; j <= cnt; j++)D[j][0] = dd, D[j][1] = 0;
			}
			continue;
		}
		long long s1 = 0, s2 = 0;
		for (j = 1; j <= cnt; j++) {
			s1 = (s1 + D[j][0]) % Mod;
			s2 = (s2 + D[j][1]) % Mod;
		}
		if (C[i] == 0) {
			dd = (s1+s2) % Mod;
			continue;
		}
		if (C[i] == 1 || C[i] == 4) {
			cnt++;
			dd = (s1+s2) * cnt % Mod;
			continue;
		}
		if (C[i] == 5) {
			cnt += 2;
			dd = (s1+s2)*cnt*(cnt - 1) % Mod;
			continue;
		}
		for (j = 0; j <= cnt + 3; j++)TD[j][0] = TD[j][1] = 0;
		if (C[i] == 2) {
			long long s = 0;
			for (j = cnt; j >= 1; j--) {
				s = (s+D[j][1])%Mod;
				TD[j][0] += s;
			}
			cnt++;
			for (j = 1; j <= cnt; j++) {
				TD[j][0] += s1;
			}
		}
		if (C[i] == 3 || C[i] == 6) {
			long long s = 0;
			for (j = cnt+1; j >= 2; j--) {
				s = (s + D[j-1][1]) % Mod;
				TD[j][0] += s*(j-1);
			}
			s = 0;
			for (j = 1; j <= cnt; j++) {
				s = (s + D[j][0]) % Mod;
				TD[j+1][1] += s*(cnt - j + 1);
			}
			cnt += 2;
			s = 0;
			for (j = cnt - 1; j >= 2; j--) {
				s = (s + D[j - 1][0]) % Mod;
				TD[j][0] += s*(j - 1);
			}
			s = 0;
			for (j = 3; j <= cnt; j++) {
				s = (s + D[j - 2][0]) % Mod;
				TD[j][0] += s*(j - 1);
			}
		}
		if (C[i] == 7) {
			cnt += 3;
			long long s = 0;
			for (j = 3; j <= cnt; j++) {
				s = (s + D[j - 2][0]) % Mod;
				TD[j][0] += (j - 1)*(j - 2)*s1;
				TD[j][1] += (j - 1)*(cnt - j)*s*2;
			}
			s = 0;
			for (j = 2; j <= cnt-2; j++) {
				s = (s + D[j - 1][0]) % Mod;
				TD[j][1] += s*(cnt - j)*(cnt - j - 1);
			}
		}
		for (j = 1; j <= cnt; j++) {
			D[j][0] = TD[j][0]%Mod;
			D[j][1] = TD[j][1]%Mod;
		}
	}
	if (w[n][2])printf("%lld\n", dd%Mod);
	else {
		long long res = 0;
		for (i = 1; i <= cnt; i++)res = (res + D[i][0]) % Mod;
		printf("%lld\n", res);
	}
}

Compilation message (stderr)

solitaire.cpp: In function 'int main()':
solitaire.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
solitaire.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", q + 1);
   ~~~~~^~~~~~~~~~~~~

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