QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #718786 | #9536. Athlete Welcome Ceremony | A_J1e# | WA | 173ms | 115244kb | C++23 | 2.8kb | 2024-11-06 21:26:36 | 2024-11-06 21:26:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
bool mem1;
void solve() {
int n, q; cin >> n >> q;
string s; cin >> s;
s = " " + s;
constexpr int mod = 1e9 + 7;
vector f(302, vector(302, array<int, 3>()));
int cnt = 0;
if (s[1] != '?') f[0][0][s[1] - 'a'] = 1;
else f[1][0][0] = 1, f[0][1][1] = 1, f[0][0][2] = 1, cnt ++;
for (int i = 2; i <= n; i ++ ) {
vector g(302, vector(302, array<int, 3>()));
for (int a = 0; a <= cnt; a ++ )
for (int b = 0; b + a <= cnt; b ++ ) {
if (s[i] != '?')
for (int k = 0; k < 3; k ++ ) {
g[a][b][s[i] - 'a'] += (k == s[i] - 'a' ? 0 : f[a][b][k]);
g[a][b][s[i] - 'a'] %= mod;
}
else {
if (a != 300)
g[a + 1][b][0] += (f[a][b][1] + f[a][b][2]) % mod,
g[a + 1][b][0] %= mod;
if (b != 300)
g[a][b + 1][1] += (f[a][b][0] + f[a][b][2]) % mod,
g[a][b + 1][1] %= mod;
if (cnt - a - b != 300)
g[a][b][2] += (f[a][b][1] + f[a][b][0]) % mod,
g[a][b][2] %= mod;
}
}
if (s[i] == '?') cnt ++;
f = move(g);
}
vector g(302, vector(302, vector<int>(302)));
for (int a = 0; a <= cnt; a ++ )
for (int b = 0; a + b <= cnt; b ++ ) {
int c = cnt - a - b;
g[a][b][c] = (f[a][b][0] + f[a][b][1] + f[a][b][2]) % mod;
}
for (int a = 0; a <= 300; a ++ )
for (int b = 0; b <= 300; b ++ )
for (int c = 0; c <= 300; c ++ )
g[a][b][c + 1] += g[a][b][c],
g[a][b][c + 1] %= mod;
for (int a = 0; a <= 300; a ++ )
for (int b = 0; b <= 300; b ++ )
for (int c = 0; c <= 300; c ++ )
g[a][b + 1][c] += g[a][b][c],
g[a][b + 1][c] %= mod;
for (int a = 0; a <= 300; a ++ )
for (int b = 0; b <= 300; b ++ )
for (int c = 0; c <= 300; c ++ )
g[a + 1][b][c] += g[a][b][c],
g[a + 1][b][c] %= mod;
while (q -- ) {
int a, b, c; cin >> a >> b >> c;
cout << g[a][b][c] << "\n";
}
}
bool mem2;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
cerr << fixed << setprecision(2) << "Memory : " << abs(&mem1 - &mem2) / 1024. / 1024. << "MB\n";
#endif
int T = 1;
while (T -- ) solve();
#ifdef LOCAL
cerr << "Time : " << clock() * 1000 / CLOCKS_PER_SEC << "MS\n";
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 173ms
memory: 115028kb
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: 166ms
memory: 115168kb
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: 152ms
memory: 115032kb
input:
1 1 ? 0 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 168ms
memory: 115024kb
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: 169ms
memory: 115176kb
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: 172ms
memory: 115096kb
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: 165ms
memory: 115108kb
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: 0
Accepted
time: 167ms
memory: 115244kb
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:
16 15 14 16 16 16 16 16 8 2 16 8 16 16 16 16 16 2 16 16 16 0 1 16 16 5 1 5 16 16 16 16 16 15 16 13 16 15 2 16 16 1 8 16 16 16 15 0 16 15 16 16 16 16 8 8 16 16 16 16 16 16 8 16 16 1 8 8 16 16 1 16 1 0 16 2 2 16 7 16 16 8 16 16 16 16 1 16 14 16 16 16 16 5 16 16 14 16 11 16 15 11 2 1 8 16 16 7 16 5 16 ...
result:
ok 1000 lines
Test #9:
score: -100
Wrong Answer
time: 158ms
memory: 115028kb
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:
195508388 259088039 939792871 858846490 10104 334198754 479284703 174283993 18944427 659694548 894876281 515985973 342761527 182802705 215438611 24903472 898235886 313982884 440599794 337549965 39088634 527160619 688006832 529480730 906092786 448494161 718236644 816152457 705467745 176823209 6667784...
result:
wrong answer 1st lines differ - expected: '490475656', found: '195508388'