QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #704866 | #9536. Athlete Welcome Ceremony | ucup-team4967# | WA | 3ms | 11144kb | C++17 | 2.7kb | 2024-11-02 21:19:24 | 2024-11-02 21:19:25 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>
#define pl(a, b) a = (a + b) % (ll)1000000007
ll dp[305][305][305][3], v[305][305], t[305][305];
ll mod = (ll)1000000007;
ll n, q, u;
int main() {
cin >> n >> q;
string s;
cin >> s;
REP(i, n) if(s[i] == '?')u++;
REP(i, n){
REP(j, i + 1){
REP(k, i + 1){
if(i == 0){
if(s[i] == 'a') pl(dp[i + 1][j][k][0], 1);
if(s[i] == 'b') pl(dp[i + 1][j][k][1], 1);
if(s[i] == 'c') pl(dp[i + 1][j][k][2], 1);
if(s[i] == '?') {
pl(dp[i + 1][j + 1][k][0], 1);
pl(dp[i + 1][j][k + 1][1], 1);
pl(dp[i + 1][j][k][2], 1);
}
}
else{
if(s[i] == 'a') {
pl(dp[i + 1][j][k][0], dp[i][j][k][1]);
pl(dp[i + 1][j][k][0], dp[i][j][k][2]);
}
if(s[i] == 'b') {
pl(dp[i + 1][j][k][1], dp[i][j][k][0]);
pl(dp[i + 1][j][k][1], dp[i][j][k][2]);
}
if(s[i] == 'c') {
pl(dp[i + 1][j][k][2], dp[i][j][k][0]);
pl(dp[i + 1][j][k][2], dp[i][j][k][1]);
}
else if(s[i] == '?'){
pl(dp[i + 1][j + 1][k][0], dp[i][j][k][1]);
pl(dp[i + 1][j + 1][k][0], dp[i][j][k][2]);
pl(dp[i + 1][j][k + 1][1], dp[i][j][k][0]);
pl(dp[i + 1][j][k + 1][1], dp[i][j][k][2]);
pl(dp[i + 1][j][k][2], dp[i][j][k][0]);
pl(dp[i + 1][j][k][2], dp[i][j][k][1]);
}
}
}
}
}
REP(i, 302){
REP(j, 302){
REP(k, 3){
pl(v[i][j], dp[n][i][j][k]);
pl(t[i][j], dp[n][i][j][k]);
}
}
}
REP(i, 302){
REP(j, 302){
pl(v[i][j + 1], v[i][j]);
}
}
REP(n, 604){
REP(i, n){
if(i + 1 > 302 or n - i > 302)continue;
pl(v[n - i - 1][i + 1], v[n - i][i]);
}
}
REP(i, 302){
REP(j, 302){
pl(t[i][j + 1], t[i][j]);
}
}
REP(i, 302){
REP(j, 302){
pl(t[i + 1][j], t[i][j]);
}
}
REP(qq, q){
ll a, b, c;
cin >> a >> b >> c;
ll m = max(0ll, u - c);
ll ans = t[a][b];
if(m - b - 2 >= 0) ans = (ans - t[m - b - 2][b] + mod) % mod;
if(m >= 1){
if(m - b - 1 >= 0) ans = (ans - v[m - b - 1][b] + mod) % mod;
else ans = (ans - v[0][m - 1] + mod) % mod;
}
if(m - a - 2 >= 0) ans = (ans + t[a + 1][m - a - 2]) % mod;
cout << ans << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 5112kb
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: 3ms
memory: 5120kb
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: 0ms
memory: 4956kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5272kb
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: 3ms
memory: 5480kb
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: -100
Wrong Answer
time: 3ms
memory: 11144kb
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 1000000006 8 8 6 8 8 8 8 0 1 0 1 8 4 8 8 8 2 4 1 8 2 6 0 2 8 6 8 8 1 4 2 8 8 0 1000000003 8 2 0 8 8 8 4 8 8 8 8 2 0 3 4 8 8 1 8 7 6 7 0 8 8 8 0 4 7 8 4 3 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:
wrong answer 4th lines differ - expected: '0', found: '1000000006'