oj.uz

Submission #781492

# Submission time Handle Problem Language Result Execution time Memory
781492 2023-07-13T06:56:04 Z 이동현(#10013) None (JOI16_solitaire) C++17
30 / 100
 276 ms 262144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int mod = (int)1e9 + 7;
int dp[304][904][2];
int comb[6004][6004];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    for(int i = 0; i < 6004; ++i){
        comb[i][0] = 1;
        for(int j = 1; j <= i; ++j){
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % mod;
        }
    }

    int n;
    cin >> n;
    vector<string> a(3);
    for(int i = 0; i < 3; ++i){
        cin >> a[i];
    }
    if(a[0][0] == 'x' || a[0][n - 1] == 'x' || a[2][0] == 'x' || a[2][n - 1] == 'x'){
        cout << "0\n";
        return 0;
    }
    for(int i = 0; i + 1 < n; ++i){
        if((a[0][i] == 'x' && a[0][i + 1] == 'x') || (a[2][i] == 'x' && a[2][i + 1] == 'x')){
            cout << "0\n";
            return 0;
        }
    }
    
    vector<int> cnt(n);
    for(int i = 0; i < n; ++i){
        cnt[i] = (a[0][i] == 'x') + (a[2][i] == 'x');
    }

    auto merge = [&](int x, int y){
        return comb[x + y][x];
    };

    vector<vector<int>> vc;
    int fact[4] = {1, 1, 2, 6};
    int gop[3] = {1, 1, 2};
    for(int i = 0; i < n; ++i){
        if(a[1][i] == 'o'){
            if(a[0][i] == 'x'){
                vc.push_back({1, 1});
            }
            if(a[2][i] == 'x'){
                vc.push_back({1, 1});
            }
            continue;
        }

        if(i){
            dp[i][0][0] = fact[cnt[i]];
            if(cnt[i] >= 1) dp[i][1][0] = cnt[i];
            if(cnt[i] >= 2) dp[i][2][0] = 2;
            dp[i][cnt[i]][1] = max(1ll, cnt[i]);
        }
        else{
            dp[i][cnt[i]][0] = dp[i][cnt[i]][1] = max(1ll, cnt[i]);
        }

        int j = i + 1;
        int sum = cnt[i] + 1;
        while(j < n && a[1][j] == 'x'){
            int psum = sum;
            sum += cnt[j] + 1;
            for(int x = cnt[j]; x < sum; ++x){
                for(int y = x - cnt[j]; y < psum; ++y){
                    (dp[j][x][0] += dp[j - 1][y][0] * merge(cnt[j], x - cnt[j]) % mod * gop[cnt[j]] % mod) %= mod;
                    (dp[j][x][1] += dp[j - 1][y][0] * merge(cnt[j], x - cnt[j]) % mod * gop[cnt[j]] % mod) %= mod;
                }
            }
            for(int x = cnt[j] + 1; x < sum; ++x){
                for(int y = 0; y < x - cnt[j]; ++y){
                    (dp[j][x][0] += dp[j - 1][y][1] * merge(cnt[j], x - cnt[j]) % mod * gop[cnt[j]] % mod) %= mod;
                    (dp[j][x][1] += dp[j - 1][y][1] * merge(cnt[j], x - cnt[j]) % mod * gop[cnt[j]] % mod) %= mod;
                }
            }
            if(cnt[j]){
                for(int x = cnt[j]; x < sum; ++x){
                    for(int y = 0; y < x - cnt[j] + 1; ++y){
                        (dp[j][x][0] += dp[j - 1][y][1] * merge(cnt[j] - 1, x - cnt[j] + 1) % mod * merge(1, psum - (x - cnt[j] + 1)) % mod * gop[cnt[j]] % mod) %= mod;
                    }
                }
            }
            if(cnt[j] > 1){
                for(int x = cnt[j] - 1; x < sum; ++x){
                    for(int y = 0; y < x - cnt[j] + 2; ++y){
                        (dp[j][x][0] += dp[j - 1][y][1] * merge(2, psum - (x - cnt[j] + 2)) % mod * gop[cnt[j]] % mod) %= mod;
                    }
                }
            }
            ++j;
        }

        --j;
        int nans = 0;
        if(j == n - 1){
            for(int k = 0; k < sum; ++k){
                nans += dp[j][k][1];
            }
        }
        else{
            for(int k = 0; k < sum; ++k){
                nans += dp[j][k][0];
            }
        }
        vc.push_back({nans, sum});
        i = j;
    }

    int ans = 1, acnt = 0;
    for(auto&i:vc){
        // cout << "COMPONENT " << i[0] << ' ' << i[1] << endl;
        ans = ans * i[0] % mod * merge(acnt, i[1]) % mod;
        acnt += i[1];
    }

    cout << ans << '\n';

    // for(int i = 0; i < n; ++i){
    //     if(a[1][i] != 'x') continue;
    //     for(int j = 0; j < 100; ++j){
    //         if(dp[i][j][0]) cout << "OPEN " << i << ' ' << j << ' ' << dp[i][j][0] << '\n';
    //     }
    //     for(int j = 0; j < 100; ++j){
    //         if(dp[i][j][1]) cout << "CLOSE " << i << ' ' << j << ' ' << dp[i][j][1] << '\n';
    //     }
    // }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164584 KB Output is correct
2 Correct 77 ms 164536 KB Output is correct
3 Correct 77 ms 164584 KB Output is correct
4 Correct 84 ms 164580 KB Output is correct
5 Correct 73 ms 164596 KB Output is correct
6 Correct 73 ms 164488 KB Output is correct
7 Correct 76 ms 164496 KB Output is correct
8 Correct 76 ms 164580 KB Output is correct
9 Correct 78 ms 164548 KB Output is correct
10 Correct 77 ms 164632 KB Output is correct
11 Correct 75 ms 164512 KB Output is correct
12 Correct 74 ms 164500 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 164756 KB Output is correct
2 Correct 73 ms 164584 KB Output is correct
3 Correct 75 ms 164620 KB Output is correct
4 Correct 74 ms 164556 KB Output is correct
5 Correct 75 ms 164588 KB Output is correct
6 Correct 74 ms 164564 KB Output is correct
7 Correct 79 ms 164684 KB Output is correct
8 Correct 75 ms 164556 KB Output is correct
9 Correct 74 ms 164588 KB Output is correct
10 Correct 73 ms 164588 KB Output is correct
11 Correct 73 ms 164608 KB Output is correct
12 Correct 73 ms 164556 KB Output is correct
13 Correct 74 ms 164724 KB Output is correct
14 Correct 72 ms 164644 KB Output is correct
15 Correct 74 ms 164672 KB Output is correct
16 Correct 73 ms 164680 KB Output is correct
17 Correct 74 ms 164684 KB Output is correct
18 Correct 73 ms 164588 KB Output is correct
19 Correct 74 ms 164692 KB Output is correct
20 Correct 73 ms 164700 KB Output is correct
21 Correct 77 ms 164628 KB Output is correct
22 Correct 74 ms 164668 KB Output is correct
23 Correct 73 ms 164596 KB Output is correct
24 Correct 74 ms 164636 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164584 KB Output is correct
2 Correct 77 ms 164536 KB Output is correct
3 Correct 77 ms 164584 KB Output is correct
4 Correct 84 ms 164580 KB Output is correct
5 Correct 73 ms 164596 KB Output is correct
6 Correct 73 ms 164488 KB Output is correct
7 Correct 76 ms 164496 KB Output is correct
8 Correct 76 ms 164580 KB Output is correct
9 Correct 78 ms 164548 KB Output is correct
10 Correct 77 ms 164632 KB Output is correct
11 Correct 75 ms 164512 KB Output is correct
12 Correct 74 ms 164500 KB Output is correct
13 Correct 86 ms 164756 KB Output is correct
14 Correct 73 ms 164584 KB Output is correct
15 Correct 75 ms 164620 KB Output is correct
16 Correct 74 ms 164556 KB Output is correct
17 Correct 75 ms 164588 KB Output is correct
18 Correct 74 ms 164564 KB Output is correct
19 Correct 79 ms 164684 KB Output is correct
20 Correct 75 ms 164556 KB Output is correct
21 Correct 74 ms 164588 KB Output is correct
22 Correct 73 ms 164588 KB Output is correct
23 Correct 73 ms 164608 KB Output is correct
24 Correct 73 ms 164556 KB Output is correct
25 Correct 74 ms 164724 KB Output is correct
26 Correct 72 ms 164644 KB Output is correct
27 Correct 74 ms 164672 KB Output is correct
28 Correct 73 ms 164680 KB Output is correct
29 Correct 74 ms 164684 KB Output is correct
30 Correct 73 ms 164588 KB Output is correct
31 Correct 74 ms 164692 KB Output is correct
32 Correct 73 ms 164700 KB Output is correct
33 Correct 77 ms 164628 KB Output is correct
34 Correct 74 ms 164668 KB Output is correct
35 Correct 73 ms 164596 KB Output is correct
36 Correct 74 ms 164636 KB Output is correct
37 Correct 74 ms 164628 KB Output is correct
38 Correct 75 ms 164812 KB Output is correct
39 Correct 74 ms 164708 KB Output is correct
40 Incorrect 75 ms 165324 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 164584 KB Output is correct
2 Correct 77 ms 164536 KB Output is correct
3 Correct 77 ms 164584 KB Output is correct
4 Correct 84 ms 164580 KB Output is correct
5 Correct 73 ms 164596 KB Output is correct
6 Correct 73 ms 164488 KB Output is correct
7 Correct 76 ms 164496 KB Output is correct
8 Correct 76 ms 164580 KB Output is correct
9 Correct 78 ms 164548 KB Output is correct
10 Correct 77 ms 164632 KB Output is correct
11 Correct 75 ms 164512 KB Output is correct
12 Correct 74 ms 164500 KB Output is correct
13 Runtime error 276 ms 262144 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -