QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #716631 | #9536. Athlete Welcome Ceremony | DepletedPrism# | WA | 238ms | 128924kb | C++17 | 5.0kb | 2024-11-06 15:41:52 | 2024-11-06 15:41:55 |
Judging History
answer
/*
* @Author: zxxzy
* @Date: 2023-11-28 15:06:53
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
#include <set>
#include <cmath>
#include <vector>
#include <map>
//#define int long long
#define space ' '
#define endl '\n'
#define de(x) cout<<"** "<<x<<" **"<<endl;
#define N 305
using namespace std;
using ll=long long;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-6;
int dp[2][N][N][N][3];
int sum[N][N][N];
signed main(){
#ifdef LOCAL
freopen("D:\\code2023\\test\\input.txt", "r", stdin);
freopen("D:\\code2023\\test\\output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
int q;
cin>>q;
// for(int i=1;i)
string s;
cin>>s;
// int n=s.size();
s="#"+s;
int cnt=0;
// for(int i=0;i<=300;i++){
// for(int j=0;j<=300;j++){
// for(int z=0;z<=300;z++){
// }
// }
// }
// for(int i=0;i<3;i++){
// dp[0][0][0][0][i]=1;
// }
int mark=0;
for(int i=1;i<=n;i++){
// int cnt=0;
if(s[i]=='?'){
// int cnt=0;
cnt++;
for(int x=0;x<=cnt;x++){
for(int y=0;y<=cnt-x;y++){
for(int z=cnt-x-y;z<=cnt-x-y;z++){
if(i==1){
dp[mark^1][1][0][0][0]=1;
dp[mark^1][0][1][0][1]=1;
dp[mark^1][0][0][1][2]=1;
continue;
}
int now=0;
// for(int kk=0;kk<3;kk++){
// if(kk==k)continue;
if(x>0){
now=(1ll*now+dp[mark][x-1][y][z][1]+dp[mark][x-1][y][z][2])%mod;
}
dp[mark^1][x][y][z][0]=now;
now=0;
if(y>0){
now=(1ll*now+dp[mark][x][y-1][z][0]+dp[mark][x][y-1][z][2])%mod;
}
dp[mark^1][x][y][z][1]=now;
now=0;
if(z>0){
now=(1ll*now+dp[mark][x][y][z-1][1]+dp[mark][x][y][z-1][0])%mod;
}
dp[mark^1][x][y][z][2]=now;
// }
// dp[mark^1][x][y][z][k]=now;
// }
}
}
}
}else{
int k=s[i]-'a';
for(int x=0;x<=cnt;x++){
for(int y=0;y<=cnt-x;y++){
for(int z=cnt-x-y;z<=cnt-x-y;z++){
if(i==1){
dp[mark^1][x][y][z][k]=1;
continue;
}
int now=0;
for(int kk=0;kk<3;kk++){
if(kk==k)continue;
now=(now+dp[mark][x][y][z][kk])%mod;
dp[mark][x][y][z][kk]=0;
}
dp[mark^1][x][y][z][k]=now;
}
}
}
}
mark^=1;
// for(int x=0;x<4;x++){
// for(int y=0;y<4;y++){
// for(int z=0;z<4;z++){
// for(int k=0;k<3;k++){
// cout<<i<<space<<x<<space<<y<<space<<z<<space<<k<<": "<<dp[mark][x][y][z][k]<<endl;
// }
// }
// }
// }
}
if(1){
for(int x=0;x<=cnt;x++){
for(int y=0;y<=cnt-x;y++){
for(int z=cnt-x-y;z<=cnt-x-y;z++){
if(s[n]=='?'){
int now=0;
for(int kk=0;kk<3;kk++){
// if(kk==k)continue;
now=(now+dp[mark][x][y][z][kk])%mod;
}
sum[x+1][y+1][z+1]=now;
}else{
sum[x+1][y+1][z+1]=dp[mark][x][y][z][s[n]-'a'];
}
}
}
}
}
for(int i=1;i<=301;i++){
for(int j=1;j<=301;j++){
for(int k=1;k<=301;k++){
// if(i+j+k!=cnt)continue;
ll now=0;
now=1ll-1ll+sum[i][j][k]+sum[i-1][j][k]+sum[i][j][k-1]+sum[i][j-1][k]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1];
sum[i][j][k]=(now%mod+mod)%mod;
}
}
}
while(q--){
int x,y,z;
cin>>x>>y>>z;
x++,y++,z++;
cout<<sum[x][y][z]<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 233ms
memory: 122964kb
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: 236ms
memory: 128924kb
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: 238ms
memory: 116848kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 238ms
memory: 117020kb
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 2 2 2 2 1 1 2 1 2
result:
wrong answer 2nd lines differ - expected: '1', found: '2'