oj.uz

Submission #49809

# Submission time Handle Problem Language Result Execution time Memory
49809 2018-06-03T09:36:41 Z 강태규(#1279, imeimi2000) None (JOI16_solitaire) C++11
10 / 100
 3 ms 764 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int mod = 1e9 + 7;
int n;
char grid[3][2001];
int dp[2001][6001][2];
int fact[6001];

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

int pow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int ret = pow(x, p >> 1);
    ret = (llong)ret * ret % mod;
    if (p & 1) ret = (llong)ret * x % mod;
    return ret;
}

int nP2(int x) {
    return (llong)x * (x - 1) % mod;
}

pii getCount(int s, int e) {
    if (e <= s) return pii(1, 0);
    int n = e - s;
    vector<int> cnt(n + 1, 0);
    vector<int> sum(n + 1, 0);
    for (int i = s; i < e; ++i) {
        cnt[i - s + 1] = (grid[0][i] == 'x') + (grid[2][i] == 'x') + 1;
        sum[i - s + 1] = sum[i - s] + cnt[i - s + 1];
    }
    dp[0][0][0] = 0;
    dp[0][0][1] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < sum[i + 1]; ++j) {
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] == 1) {
            for (int j = 1; j <= sum[i]; ++j) {
                dp[i][j][0] = 0;
                
                dp[i][j][1] = dp[i - 1][sum[i - 1]][1];
                dp[i][j][1] += dp[i - 1][sum[i - 1]][0];
                dp[i][j][1] %= mod;
                dp[i][j][1] += mod - dp[i - 1][j - 1][0];
                dp[i][j][1] %= mod;
            }
        }
        else if (cnt[i] == 2) {
            for (int j = 1; j <= sum[i]; ++j) {
                dp[i][j][0] = (llong)dp[i - 1][j - 1][1] * (sum[i] - j) % mod;
                
                dp[i][j][1] = (llong)dp[i - 1][sum[i - 1]][1] * (j - 1) % mod;
                if (j > 1) dp[i][j][1] += (llong)(dp[i - 1][sum[i - 1]][0] - dp[i - 1][j - 2][0] + mod) * (j - 1) % mod;
                dp[i][j][1] %= mod;
            }
        }
        else {
            for (int j = 1; j <= sum[i]; ++j) {
                dp[i][j][0] = (llong)dp[i - 1][j - 1][1] * nP2(sum[i] - j) % mod;
                if (j > 1) dp[i][j][0] += (llong)dp[i - 1][j - 2][1] * (sum[i] - j) % mod * (j - 1) * 2 % mod;
                dp[i][j][0] %= mod;
                
                dp[i][j][1] = (llong)dp[i - 1][sum[i - 1]][1] * nP2(j - 1) % mod;
                dp[i][j][1] += (llong)(dp[i - 1][sum[i - 1]][0] - dp[i - 1][j - 1][0] + mod) * nP2(j - 1) % mod;
                dp[i][j][1] %= mod;
            }
        }
        for (int j = 1; j <= sum[i]; ++j) {
            dp[i][j][0] += dp[i][j - 1][0];
            dp[i][j][0] %= mod;
            dp[i][j][1] += dp[i][j - 1][1];
            dp[i][j][1] % mod;
        }
    }
    return pii((dp[n][sum[n]][0] + dp[n][sum[n]][1]) % mod, sum[n]);
}



int main() {
    scanf("%d", &n);
    scanf("%s", grid[0]);
    scanf("%s", grid[1]);
    scanf("%s", grid[2]);
    if (grid[0][0] == 'x') fail();
    if (grid[2][0] == 'x') fail();
    if (grid[0][n - 1] == 'x') fail();
    if (grid[2][n - 1] == 'x') fail();
    for (int i = 1; i < n - 2; ++i) {
        if (grid[0][i] == 'x' && grid[0][i + 1] == 'x') fail();
        if (grid[2][i] == 'x' && grid[2][i + 1] == 'x') fail();
    }
    fact[0] = 1;
    for (int i = 1; i <= 3 * n; ++i) {
        fact[i] = (llong)fact[i - 1] * i % mod;
    }
    vector<pii> ans;
    int p = 0;
    for (int i = 0; i < n; ++i) {
        if (grid[1][i] == 'o') {
            ans.push_back(getCount(p, i));
            int c = (grid[0][i] == 'x') + (grid[2][i] == 'x');
            if (c) ans.emplace_back(c, c);
            p = i + 1;
        }
    }
    ans.push_back(getCount(p, n));
    int sum = 0;
    for (pii i : ans) {
        sum += i.second;
    }
    
    int x = fact[sum], y = 1;
    for (pii i : ans) {
        x = (llong)x * i.first % mod;
        y = (llong)y * fact[i.second] % mod;
    }
    x = (llong)x * pow(y, mod - 2) % mod;
    printf("%d\n", x);
	return 0;
}

Compilation message

solitaire.cpp: In function 'pii getCount(int, int)':
solitaire.cpp:98:25: warning: statement has no effect [-Wunused-value]
             dp[i][j][1] % mod;
             ~~~~~~~~~~~~^~~~~
solitaire.cpp: In function 'int main()':
solitaire.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
solitaire.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", grid[0]);
     ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", grid[1]);
     ~~~~~^~~~~~~~~~~~~~~
solitaire.cpp:110:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", grid[2]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 428 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 708 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Incorrect 2 ms 764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 428 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 708 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 2 ms 748 KB Output is correct
19 Correct 2 ms 748 KB Output is correct
20 Correct 2 ms 748 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Incorrect 2 ms 764 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 428 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 2 ms 668 KB Output is correct
8 Correct 2 ms 668 KB Output is correct
9 Correct 2 ms 668 KB Output is correct
10 Correct 2 ms 668 KB Output is correct
11 Correct 2 ms 668 KB Output is correct
12 Correct 2 ms 708 KB Output is correct
13 Incorrect 3 ms 740 KB Output isn't correct
14 Halted 0 ms 0 KB -