QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #726454 | #9536. Athlete Welcome Ceremony | gt1h | TL | 1946ms | 207184kb | C++17 | 7.6kb | 2024-11-09 00:54:53 | 2024-11-09 00:54:53 |
Judging History
answer
#include<bits/stdc++.h>
#define ioss ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define int long long
using namespace std;
const int mod=1e9+7;
int n,q,x,y,z,c0,c1,c2;
int ans[155][155][155];
int dp[155][155][155][3],dpp[155][155][155][3];
string s;
inline void gin(int &x){
x=0; int nt;
while(!isdigit(nt=getchar())); x=nt^'0';
while(isdigit(nt=getchar())) x=(x<<1)+(x<<3)+(nt^'0');
}
inline void prt(const int &x) {
if(x>9) prt(x/10);
putchar((x%10)^'0');
}
inline void f() {
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=0;
if (s[0]=='a') {
if (i>0)
dp[i][j][k][0]=1;
}
if (s[0]=='b') {
if (j>0)
dp[i][j][k][1]=1;
}
if (s[0]=='c') {
if (k>0)
dp[i][j][k][2]=1;
}
if (s[0]=='?') {
if (i>0)
dp[i][j][k][0]=1;
if (j>0)
dp[i][j][k][1]=1;
if (k>0)
dp[i][j][k][2]=1;
}
}
}
}
dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
int l=s.size();
if (l==1) {
if (s[0]=='?') {
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
if (i>0)
ans[i][j][k]+=1;
if (j>0)
ans[i][j][k]+=1;
if (k>0)
ans[i][j][k]+=1;
}
}
}
}
else {
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
ans[i][j][k]=1;
}
}
}
}
return ;
}
for (int x=1;x<l;++x) {
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
for (int c=0;c<=2;++c) {
dpp[i][j][k][c]=dp[i][j][k][c];
}
}
}
}
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
dpp[i][j][k][0]=dpp[i][j][k][1]=dpp[i][j][k][2]=0;
if (s[x]=='a') {
if (i==0)
continue;
if (s[x-1]=='b') {
dpp[i][j][k][0]=dp[i-1][j][k][1];
}
if (s[x-1]=='c') {
dpp[i][j][k][0]=dp[i-1][j][k][2];
}
if (s[x-1]=='?') {
dpp[i][j][k][0]=(dp[i-1][j][k][1]+dp[i-1][j][k][2])%mod;
}
}
if (s[x]=='b') {
if (j==0)
continue;
if (s[x-1]=='a') {
dpp[i][j][k][1]=dp[i][j-1][k][0];
}
if (s[x-1]=='c') {
dpp[i][j][k][1]=dp[i][j-1][k][2];
}
if (s[x-1]=='?') {
dpp[i][j][k][1]=(dp[i][j-1][k][0]+dp[i][j-1][k][2])%mod;
}
}
if (s[x]=='c') {
if (k==0)
continue;
if (s[x-1]=='a') {
dpp[i][j][k][2]=dp[i][j][k-1][0];
}
if (s[x-1]=='b') {
dpp[i][j][k][2]=dp[i][j][k-1][1];
}
if (s[x-1]=='?') {
dpp[i][j][k][2]=(dp[i][j][k-1][0]+dp[i][j][k-1][1])%mod;
}
}
if (s[x]=='?') {
if (s[x-1]=='a') {
if (j>0)
dpp[i][j][k][1]=dp[i][j-1][k][0];
if (k>0)
dpp[i][j][k][2]=dp[i][j][k-1][0];
}
if (s[x-1]=='b') {
if (i>0)
dpp[i][j][k][0]=dp[i-1][j][k][1];
if (k>0)
dpp[i][j][k][2]=dp[i][j][k-1][1];
}
if (s[x-1]=='c') {
if (i>0)
dpp[i][j][k][0]=dp[i-1][j][k][2];
if (j>0)
dpp[i][j][k][1]=dp[i][j-1][k][2];
}
if (s[x-1]=='?') {
if (i>0)
dpp[i][j][k][0]=(dp[i-1][j][k][1]+dp[i-1][j][k][2])%mod;
if (j>0)
dpp[i][j][k][1]=(dp[i][j-1][k][0]+dp[i][j-1][k][2])%mod;
if (k>0)
dpp[i][j][k][2]=(dp[i][j][k-1][0]+dp[i][j][k-1][1])%mod;
}
}
}
}
}
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
for (int c=0;c<=2;++c) {
dp[i][j][k][c]=dpp[i][j][k][c];
}
}
}
}
}
for (int i=0;i<=150;++i) {
for (int j=0;j<=150;++j) {
for (int k=0;k<=150;++k) {
if (s[l-1]=='a') {
ans[i][j][k]=dp[i][j][k][0];
}
if (s[l-1]=='b') {
ans[i][j][k]=dp[i][j][k][1];
}
if (s[l-1]=='c') {
ans[i][j][k]=dp[i][j][k][2];
}
if (s[l-1]=='?') {
if (s[l-2]=='a') {
ans[i][j][k]=(dp[i][j][k][1]+dp[i][j][k][2])%mod;
}
if (s[l-2]=='b') {
ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][2])%mod;
}
if (s[l-2]=='c') {
ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][1])%mod;
}
if (s[l-2]=='?') {
ans[i][j][k]=(dp[i][j][k][0]+dp[i][j][k][1]+dp[i][j][k][2])%mod;
}
}
}
}
}
}
signed main() {
// ioss
gin(n);
gin(q);
cin>>s;
for (int i=0;i<s.size();++i) {
if (s[i]=='a')
++c0;
if (s[i]=='b')
++c1;
if (s[i]=='c')
++c2;
}
f();
while (q--) {
gin(x);
gin(y);
gin(z);
x+=c0;
y+=c1;
z+=c2;
if (x>150)
x=150;
if (y>150)
y=150;
if (z>150)
z=150;
prt(ans[x][y][z]);
putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 203ms
memory: 206476kb
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: 223ms
memory: 206968kb
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: 8ms
memory: 121180kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 344ms
memory: 206540kb
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: 363ms
memory: 206964kb
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: 1843ms
memory: 207184kb
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: 1946ms
memory: 206544kb
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: -100
Time Limit Exceeded
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 ...