QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#734627	#9536. Athlete Welcome Ceremony	Dixiky_215	WA	1591ms	395832kb	C++20	3.4kb	2024-11-11 13:27:05	2024-11-11 13:27:05

Judging History

This is the latest submission verdict.

[2024-11-11 13:27:05]
Judged

Verdict: WA
Time: 1591ms
Memory: 395832kb

Show

[2024-11-11 13:27:05]
Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MAXN=5e5+7;
int t;
int a[MAXN];
int n,m;
string b;
ll dp[2][303][303][303][4];
ll ans[303][303][303];
ll mod=1e9+7LL;
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    
    cin>>n>>m;
    cin>>b;
    b=' '+b;
    
    if(b[1]=='?')
    {
        dp[0][0][0][1][3]=1LL;
        dp[0][0][1][0][2]=1LL;
        dp[0][1][0][0][1]=1LL;
    }
    else
    {
        dp[0][0][0][0][b[1]-'a'+1]=1LL;
    }
    for(int i=2;i<=n;i++)
    {
        if(b[i]=='?')
        {
            for(int s1=0;s1<=n;s1++)
            {
                for(int s2=0;s2<=n;s2++)
                {
                    for(int s3=0;s3<=n;s3++)
                    {
                        if(s1>0) dp[1][s1][s2][s3][1]+=dp[0][s1-1][s2][s3][2]+dp[0][s1-1][s2][s3][3];
                        if(s2>0) dp[1][s1][s2][s3][2]+=dp[0][s1][s2-1][s3][1]+dp[0][s1][s2-1][s3][3];
                        if(s3>0) dp[1][s1][s2][s3][3]+=dp[0][s1][s2][s3-1][1]+dp[0][s1][s2][s3-1][2];
                        dp[1][s1][s2][s3][1]%=mod;
                        dp[1][s1][s2][s3][2]%=mod;
                        dp[1][s1][s2][s3][3]%=mod;
                    }
                }
            }
        }
        else
        {
            for(int s1=0;s1<=n;s1++)
            {
                for(int s2=0;s2<=n;s2++)
                {
                    for(int s3=0;s3<=n;s3++)
                    {
                        if(b[i]=='a')
                        {
                            dp[1][s1][s2][s3][1]+=dp[0][s1][s2][s3][2]+dp[0][s1][s2][s3][3];
                            dp[1][s1][s2][s3][1]%=mod;
                        }
                        else if(b[i]=='b')
                        {
                            dp[1][s1][s2][s3][2]+=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][3];
                            dp[1][s1][s2][s3][2]%=mod;
                        }
                        else
                        {
                            dp[1][s1][s2][s3][3]+=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][2];
                            dp[1][s1][s2][s3][3]%=mod;
                        }
                    }
                }
            }
        }

        for(int s1=0;s1<=n;s1++)
        {
            for(int s2=0;s2<=n;s2++)
            {
                for(int s3=0;s3<=n;s3++)
                {
                    for(int k=1;k<=3;k++)
                    {
                        dp[0][s1][s2][s3][k]=dp[1][s1][s2][s3][k];
                        dp[1][s1][s2][s3][k]=0;
                    }
                }
            }
        }
    }
    // cerr<<dp[0][1][1][1]<<" sad"<<endl;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=n+1;j++)
        {
            for(int k=1;k<=n+1;k++)
            {
                int s1=i-1,s2=j-1,s3=k-1;
                ll sumk=dp[0][s1][s2][s3][1]+dp[0][s1][s2][s3][2]+dp[0][s1][s2][s3][3];
                sumk+=ans[i-1][j][k]+ans[i][j-1][k]+ans[i][j][k-1];
                sumk-=ans[i-1][j-1][k]+ans[i-1][j][k-1]+ans[i][j-1][k-1];
                sumk+=ans[i-1][j-1][k-1];
                ans[i][j][k]=sumk%mod;
            }
        }
    }
    while(m--)
    {
        int s1,s2,s3;
        cin>>s1>>s2>>s3;
        cout<<ans[s1+1][s2+1][s3+1]<<'\n';
    }
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 20276kb

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

memory: 22516kb

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

memory: 7928kb

input:

1 1
?
0 1 1

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 0ms

memory: 9064kb

input:

output:

result:

ok 10 lines

Test #5:

score: 0

Accepted

time: 0ms

memory: 10968kb

input:

output:

result:

ok 10 lines

Test #6:

score: 0

Accepted

time: 54ms

memory: 44332kb

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

memory: 151332kb

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

memory: 387696kb

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

memory: 395832kb

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 2nd lines differ - expected: '143989836', found: '-856010171'