Submission #117915

#	Time	Username	Problem	Language	Result	Execution time	Memory
117915		sebinkim	Solitaire (JOI16_solitaire)	C++14	20 / 100	2050 ms	8148 KiB

solitaire

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

char A[2020], B[2020], C[2020];
ll dp[2020][6060], S[2020];
ll n, ans;

void die() { printf("0\n"); exit(0); }

int main()
{
	ll i, j, k, x, s, s1, s2, t1, t2;

	scanf("%lld%s%s%s", &n, A + 1, B + 1, C + 1);

	if(A[1] == 'x' || A[n] == 'x') die();
	if(C[1] == 'x' || C[n] == 'x') die();

	for(i=1; i<n; i++){
		if(A[i] == 'x' && A[i + 1] == 'x') die();
		if(C[i] == 'x' && C[i + 1] == 'x') die();
	}

	dp[0][0] = 1;

	for(i=1; i<=n; i++){
		S[i] = S[i - 1] + (A[i] == 'x') + (B[i] == 'x') + (C[i] == 'x');
		s = S[i];

		if(B[i] == 'o'){
			if(A[i] == 'x' && C[i] == 'x') t1 = 0;
			else if(A[i] == 'x' || C[i] == 'x') t1 = 1;
			else t1 = 2;

			for(k=0; k<=s; k++){
				if(t1 == 0) dp[i][0] = (dp[i][0] + dp[i - 1][k] * s * (s - 1)) % mod;
				else if(t1 == 1) dp[i][0] = (dp[i][0] + dp[i - 1][k] * s) % mod;
				else dp[i][0] = (dp[i][0] + dp[i - 1][k]) % mod;
			}

			if(B[i - 1] == 'o' || i < 3) continue;

			s2 = S[i - 2];
			if(A[i - 1] == 'x' && C[i - 1] == 'x') t2 = 0;
			else if(A[i - 1] == 'x' || C[i - 1] == 'x') t2 = 1;
			else t2 = 2;

			for(k=0; k<=s; k++){
				if(t2 == 0){
					x = k * (s2 - k + 2) * (s2 - k + 1) / 2 * 2 % mod;
					x = (x + (s2 - k + 3) * (s2 - k + 2) * (s2 - k + 1) / 6 * 4) % mod;
				}
				else if(t2 == 1) x = (s2 - k + 2) * (s2 - k + 1) / 2 % mod;
				else x = 0;

				x = x * dp[i - 2][k] % mod;

				if(t1 == 0) dp[i][0] = (dp[i][0] + x * s * (s - 1)) % mod;
				else if(t1 == 1) dp[i][0] = (dp[i][0] + x * s) % mod;
				else dp[i][0] = (dp[i][0] + x) % mod;
			}
		}
		else{
			if(A[i] == 'x' && C[i] == 'x') t1 = 0;
			else if(A[i] == 'x' || C[i] == 'x') t1 = 1;
			else t1 = 2;

			for(j=1; j<=s; j++){
				for(k=0; k<=s; k++){
					if(t1 == 0) dp[i][j] = (dp[i][j] + dp[i - 1][k] * (j - 1) * (j - 2)) % mod;
					else if(t1 == 1) dp[i][j] = (dp[i][j] + dp[i - 1][k] * (j - 1)) % mod;
					else dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;
				}
			}

			if(B[i - 1] == 'o' || i < 3) continue;

			s2 = S[i - 2];
			s1 = s2 + S[i] - S[i - 1];
			if(A[i - 1] == 'x' && C[i - 1] == 'x') t2 = 0;
			else if(A[i - 1] == 'x' || C[i - 1] == 'x') t2 = 1;
			else t2 = 2;

			for(j=1; j<=s; j++){
				for(k=0; k<=s; k++){
					if(t1 == 0) x = dp[i - 2][k] * (j - 1) * (j - 2) % mod;
					else if(t1 == 1) x = dp[i - 2][k] * (j - 1) % mod;
					else x = dp[i - 2][k];

					if(j < k + 3 - t1){
						if(t2 == 0){
							dp[i][j] = (dp[i][j] + x * (s1 - k + t1) * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 6 * 4) % mod;
							dp[i][j] = (dp[i][j] + x * (k + 3 - t1 - j) * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 2 * 2) % mod;
							dp[i][j + 1] = (dp[i][j + 1] + x * j * (s1 - k + t1 - 1) * (s1 - k + t1 - 1) / 2 * 2) % mod;
						}
						else if(t2 == 1){
							dp[i][j] = (dp[i][j] + x * (s1 - k + t1 - 1) * (s1 - k + t1 - 2) / 2) % mod;
						}
					}
					else{
						if(t2 == 0){
							dp[i][j] = (dp[i][j] + x * (s1 - j + 3) * (s1 - j + 2) * (s1 - j + 1) / 6 * 4) % mod;
							dp[i][j + 1] = (dp[i][j + 1] + x * j * (s1 - j + 2) * (s1 - j + 1) / 2 * 2) % mod;
						}
						else if(t2 == 1){
							dp[i][j] = (dp[i][j] + x * (s1 - j + 2) * (s1 - j + 1) / 2) % mod;			
						}
					}
				}
			}

			dp[i][s + 1] = 0;
		}
	}

	s = S[n];

	for(i=0; i<=s; i++){
		ans = (ans + dp[n][i]) % mod;
	}

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

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

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