QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785601#9536. Athlete Welcome CeremonyMagical_KingdomWA 373ms395180kbC++175.0kb2024-11-26 18:28:452024-11-26 18:28:45

Judging History

This is the latest submission verdict.

  • [2024-11-26 18:28:45]
  • Judged
  • Verdict: WA
  • Time: 373ms
  • Memory: 395180kb
Show
  • [2024-11-26 18:28:45]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 305;
int n, q;
ll dp[3][maxn][maxn][maxn];
int a[maxn];
int idx[maxn], cnt;

ll d[maxn][maxn][maxn];
ll sum[maxn][maxn][maxn];

bool check(int pos, int x) {
    pos = idx[pos];
    if (a[pos - 1] != x && a[pos + 1] != x) {
        return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    string s;
    cin >> s;
    s = " " + s;
    a[n + 1] = 9150;
    a[0] = 9150;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'a')
            a[i] = 0;
        else if (s[i] == 'b')
            a[i] = 1;
        else if (s[i] == 'c')
            a[i] = 2;
        else {
            a[i] = -8;
            idx[++cnt] = i;
        }
    }

    for (int i = 0; i <= cnt; i++) {
        for (int j = 0; i + j <= cnt; j++) {
            for (int k = 0; i + j + k <= cnt; k++) {
                if (i == 0 && j == 0 && k == 0) {
                    continue;
                }
                int pos = i + j + k;
                if (pos == 1) {
                    if (i == 1 && check(1, 0))
                        dp[0][i][j][k] = 1;
                    if (j == 1 && check(1, 1))
                        dp[1][i][j][k] = 1;
                    if (k == 1 && check(1, 2))
                        dp[2][i][j][k] = 1;
                } else {
                    if (a[idx[pos] - 1] < 0) {
                        //?
                        if (i >= 1 && check(pos, 0)) {
                            dp[0][i][j][k] = (dp[1][i - 1][j][k] + dp[2][i - 1][j][k]) % mod;
                            dp[0][i][j][k] %= mod;
                        }
                        if (j >= 1 && check(pos, 1)) {
                            dp[1][i][j][k] = (dp[0][i][j - 1][k] + dp[2][i][j - 1][k]) % mod;
                            dp[1][i][j][k] %= mod;
                        }
                        if (k >= 1 && check(pos, 2)) {
                            dp[2][i][j][k] = (dp[0][i][j][k - 1] + dp[1][i][j][k - 1]) % mod;
                            dp[2][i][j][k] %= mod;
                        }
                    } else {
                        if (i >= 1 && check(pos, 0)) {
                            dp[0][i][j][k] = (dp[0][i - 1][j][k] + dp[1][i - 1][j][k] + dp[2][i - 1][j][k]) % mod;
                            dp[0][i][j][k] %= mod;
                        }
                        if (j >= 1 && check(pos, 1)) {
                            dp[1][i][j][k] = (dp[0][i][j - 1][k] + dp[1][i][j - 1][k] + dp[2][i][j - 1][k]) % mod;
                            dp[1][i][j][k] %= mod;
                        }
                        if (k >= 1 && check(pos, 2)) {
                            dp[2][i][j][k] = (dp[0][i][j][k - 1] + dp[1][i][j][k - 1] + dp[2][i][j][k - 1]) % mod;
                            dp[2][i][j][k] %= mod;
                        }
                    }
                }
            }
        }
    }

    // for (int i = 1; i <= cnt; i++) {
    //     cerr << "i=" << i << endl;
    //     for (int j = 1; j <= cnt; j++) {
    //         for (int k = 1; k <= cnt; k++) {
    //             for (int p = 0; p <= 2; p++) {
    //                 cerr << dp[p][i][j][k] << '/';
    //             }
    //             cerr << ' ';
    //         }
    //         cerr << '\n';
    //     }
    // }

    for (int i = 0; i <= cnt; i++) {
        for (int j = 0; i + j <= cnt; j++) {
            int k = cnt - i - j;
            d[i][j][k] += (dp[0][i][j][k] + dp[1][i][j][k] + dp[2][i][j][k]) % mod;
            d[i][j][k] %= mod;
        }
    }

    for (int i = 0; i <= 300; i++) {
        for (int j = 0; j <= 300; j++) {
            for (int k = 0; k <= 300; k++) {
                sum[i][j][k] = d[i][j][k] % mod;
                if (i - 1 >= 0) {
                    (sum[i][j][k] += sum[i - 1][j][k]) % mod;
                }
                if (j - 1 >= 0) {
                    (sum[i][j][k] += sum[i][j - 1][k]) % mod;
                }
                if (k - 1 >= 0) {
                    (sum[i][j][k] += sum[i][j][k - 1]) % mod;
                }
                if (i - 1 >= 0 && j - 1 >= 0) {
                    sum[i][j][k] = (sum[i][j][k] - sum[i - 1][j - 1][k] + mod) % mod;
                }
                if (i - 1 >= 0 && k - 1 >= 0) {
                    sum[i][j][k] = (sum[i][j][k] - sum[i - 1][j][k - 1] + mod) % mod;
                }
                if (j - 1 >= 0 && k - 1 >= 0) {
                    sum[i][j][k] = (sum[i][j][k] - sum[i][j - 1][k - 1] + mod) % mod;
                }
                if (i - 1 >= 0 && j - 1 >= 0 && k - 1 >= 0) {
                    (sum[i][j][k] += sum[i - 1][j - 1][k - 1]) % mod;
                }
            }
        }
    }

    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        cout << sum[x][y][z] << '\n';
    }
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 373ms
memory: 230388kb

input:

6 3
a?b??c
2 2 2
1 1 1
1 0 2

output:

3
1
1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 358ms
memory: 234632kb

input:

6 3
??????
2 2 2
2 3 3
3 3 3

output:

30
72
96

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 363ms
memory: 228212kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 368ms
memory: 226112kb

input:

10 10
acab?cbaca
0 2 0
1 1 2
4 2 3
1 1 1
3 5 1
0 5 2
2 2 0
1 2 5
4 3 0
1 1 3

output:

0
1
1
1
1
0
1
1
1
1

result:

ok 10 lines

Test #5:

score: 0
Accepted
time: 352ms
memory: 230220kb

input:

10 10
?c?c?cbac?
10 5 1
5 8 7
9 2 6
5 7 1
5 2 6
5 6 5
5 10 3
9 1 10
2 5 9
1 2 9

output:

16
16
11
16
11
16
16
5
11
0

result:

ok 10 lines

Test #6:

score: 0
Accepted
time: 367ms
memory: 228232kb

input:

50 100
?abacbacab?cbcbcb?acabcbabcbcacbababc?caba?acacbca
8 3 8
2 4 8
8 7 3
0 9 2
10 8 7
7 6 5
4 10 2
6 9 3
3 6 6
9 10 8
2 5 8
8 1 0
3 5 0
1 0 6
5 0 8
6 5 5
1 7 9
7 7 10
4 7 5
6 6 4
10 1 2
4 1 7
10 0 8
7 6 3
1 9 1
4 7 2
8 4 0
8 6 1
5 10 4
5 8 2
5 8 4
4 5 9
5 2 1
1 10 9
4 10 1
8 4 3
8 9 9
8 0 1
0 8 0...

output:

8
8
8
0
8
8
6
8
8
8
8
0
0
0
1
8
4
8
8
8
2
4
1
8
1
6
0
2
8
6
8
8
1
4
2
8
8
0
0
8
2
0
8
8
8
4
8
8
8
8
2
0
0
4
8
8
1
8
7
6
7
0
8
8
8
0
4
7
8
4
0
8
0
4
8
8
8
7
8
4
7
2
8
8
8
0
2
2
8
8
8
4
4
0
8
0
8
8
1
1

result:

ok 100 lines

Test #7:

score: 0
Accepted
time: 361ms
memory: 255388kb

input:

50 100
b????????bca?????c?b??ca?acac?b?b???ca?ab???a?a???
35 43 36
12 49 47
7 11 34
38 44 22
42 17 10
49 8 38
18 26 44
6 18 14
28 29 6
48 32 47
29 15 48
1 5 33
24 17 18
10 27 32
19 10 34
2 23 9
14 24 39
46 12 34
9 49 26
21 8 46
43 43 3
31 16 2
8 27 7
24 41 35
17 25 31
0 13 47
24 31 23
33 40 30
36 39...

output:

34272000
31599360
497244
34272000
17637520
12290752
34272000
93044
415832
34272000
34272000
0
34272000
16360704
27933952
0
34272000
33886976
7896832
12290752
718
24
0
34272000
34272000
0
34272000
34272000
34272000
32254720
0
5666944
34256640
34272000
34272000
12290752
30493248
34256640
20630016
0
10...

result:

ok 100 lines

Test #8:

score: 0
Accepted
time: 368ms
memory: 228284kb

input:

100 1000
c?cbababcabacbacbacacbacabcbabababacababcbcab?cbabacbacbcbcacbab?bcabcbcababcacbabacbcb?babcbab?baca
13 11 4
4 17 20
14 5 2
16 14 15
8 12 17
19 5 11
5 17 12
20 7 6
19 10 1
6 5 0
13 1 9
7 17 1
20 4 16
11 12 18
19 2 16
18 1 11
19 16 3
7 1 0
6 9 16
6 9 16
6 20 7
0 16 20
1 2 8
16 5 20
18 14 18
...

output:

16
15
14
16
16
16
16
16
8
2
16
8
16
16
16
16
16
2
16
16
16
0
1
16
16
5
1
5
16
16
16
16
16
15
16
13
16
15
2
16
16
1
8
16
16
16
15
0
16
15
16
16
16
16
8
8
16
16
16
16
16
16
8
16
16
1
8
8
16
16
1
16
1
0
16
2
2
16
7
16
16
8
16
16
16
16
1
16
14
16
16
16
16
5
16
16
14
16
11
16
15
11
2
1
8
16
16
7
16
5
16
...

result:

ok 1000 lines

Test #9:

score: -100
Wrong Answer
time: 358ms
memory: 395180kb

input:

100 1000
?????c??????????????????????????b???a????a?????????????????????????c????????????????????????????????
43 38 20
27 40 32
39 27 33
28 50 43
50 3 46
38 46 14
42 48 10
45 25 28
49 10 49
38 17 42
41 49 22
41 18 44
46 47 25
17 44 35
34 43 22
47 42 32
32 44 40
36 41 24
45 38 45
49 44 18
42 34 32
43...

output:

490475656
1143989843
1119661936
4707864495
10104
1219100558
479284703
764218529
1903846238
659694548
1204287070
105920502
2191779518
182802705
1215438618
4938692346
1797581211
1903917427
-4106004207
1287222631
578695829
4095654877
1457810433
1709349802
2085961858
-76669513
-1216992508
1111119725
129...

result:

wrong answer 2nd lines differ - expected: '143989836', found: '1143989843'
English 繁體中文 简体中文

Server Time: 2025-02-06 21:38:35 | OpenSource Project