QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#750629	#9536. Athlete Welcome Ceremony	Zhangyq	WA	215ms	447304kb	C++17	3.1kb	2024-11-15 15:15:14	2024-11-15 15:15:16

Judging History

This is the latest submission verdict.

[2024-11-15 15:15:16]
Judged

Verdict: WA
Time: 215ms
Memory: 447304kb

Show

[2024-11-15 15:15:14]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define ull unsigned long long
#define endl '\n'
typedef long long ll;
typedef pair<int, int> PII;
const int N = 310, M = 5e3 + 10, INF = 1e18, mod = 998244353;
// const int P1 = 6907, P2 = 13331, mod1 = 998244353, mod2 = 1e9+9;

int f[N][N][N];
int dp[N][N][N][3];

void solve()
{
    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;
    s = " " + s;
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; i++)
        cnt[i] = cnt[i - 1] + (s[i] == '?');

    if (s[1] == 'a')
        dp[1][0][0][0] = 1;
    else if (s[1] == 'b')
        dp[1][0][0][1] = 1;
    else if (s[1] == 'c')
        dp[1][0][0][2] = 1;
    else
        dp[1][1][0][0] = 1, dp[1][0][1][1] = 1, dp[1][0][0][2] = 1;

    for (int c = 2; c <= n; c++)
        for (int i = 0; i <= cnt[c]; i++)
            for (int j = 0; i + j <= cnt[c]; j++)
            {
                if (s[c] == 'a')
                {
                    dp[c][i][j][0] = (dp[c - 1][i][j][1] + dp[c-1][i][j][2]) % mod;
                    continue;
                }
                else if (s[c] == 'b')
                {
                    dp[c][i][j][1] = (dp[c - 1][i][j][0] + dp[c - 1][i][j][2]) % mod;
                    continue;
                }
                else if (s[c] == 'c')
                {
                    dp[c][i][j][2] = (dp[c - 1][i][j][0] + dp[c - 1][i][j][1]) % mod;
                    continue;
                }

                if (i)
                    dp[c][i][j][0] = (dp[c - 1][i - 1][j][1] + dp[c - 1][i - 1][j][2]) % mod;
                if (j)
                    dp[c][i][j][1] = (dp[c - 1][i][j - 1][0] + dp[c - 1][i][j - 1][2]) % mod;
                if (cnt[c] - i - j)
                    dp[c][i][j][2] = (dp[c - 1][i][j][0] + dp[c - 1][i][j][1]) % mod;
            }

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

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

    while(q--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        cout << f[x][y][z] << endl;
    }
}

signed main()
{
    ios;
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 168ms

memory: 237056kb

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: 215ms

memory: 238524kb

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: 151ms

memory: 227800kb

input:

1 1
?
0 1 1

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 195ms

memory: 245292kb

input:

output:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 184ms

memory: 245752kb

input:

output:

result:

ok 10 lines

Test #6:

score: 0

Accepted

time: 184ms

memory: 329768kb

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:

result:

ok 100 lines

Test #7:

score: 0

Accepted

time: 159ms

memory: 332968kb

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:

result:

ok 100 lines

Test #8:

score: 0

Accepted

time: 155ms

memory: 430504kb

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:

result:

ok 1000 lines

Test #9:

score: -100

Wrong Answer

time: 149ms

memory: 447304kb

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:

result:

wrong answer 1st lines differ - expected: '490475656', found: '804458366'