oj.uz

Submission #117915

# Submission time Handle Problem Language Result Execution time Memory
117915 2019-06-17T12:22:48 Z sebinkim None (JOI16_solitaire) C++14
20 / 100
 2000 ms 8148 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 5708 KB Output is correct
2 Execution timed out 2050 ms 8148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 2 ms 512 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Incorrect 2 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -