QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#701020#9536. Athlete Welcome Ceremonyucup-team5657#WA 10ms29156kbC++142.2kb2024-11-02 13:39:442024-11-02 13:39:44

Judging History

This is the latest submission verdict.

  • [2024-11-02 13:39:44]
  • Judged
  • Verdict: WA
  • Time: 10ms
  • Memory: 29156kb
Show
  • [2024-11-02 13:39:44]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pr;
#define fi first
#define se second
#define mkp make_pair
#define pb emplace_back
// #define mid ((l+r)>>1)
#define popcnt __builtin_popcountll
const ll mod = 998244353;
inline ll read(){
	ll x=0, f=1; char ch=getchar();
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
	return x*f;
}
inline ll lg2(ll x){ return 63^__builtin_clzll(x); }
inline ll qpow(ll a,ll b){
	ll ans=1, base=a;
	while(b){
		if(b&1) ans=ans*base%mod;
		base=base*base%mod; b>>=1;
	}
	return ans;
}
void init(){ }
int f[3][305][305][305], g[305][305][305], n, q;
int ans[305][305][305];
char st[305];

void addmod(int &x){
	if(x >= mod) x -= mod;
}
void procedure(){
	n=read(),q=read();
	scanf("%s", st+1);
	f[0][0][0][0]=1;

	int a=0,b=0,c=0;
	for(int i=0;i<n;i++){
		if(st[i+1]=='a') a++;
		if(st[i+1]=='b') b++;
		if(st[i+1]=='c') c++;
		for(int j=0;j<=i;j++){
			for(int k=0;j+k<=i;k++){
				for(int s=0;s<=2;s++){
					if(!f[s][i][j][k]) continue;
					for(int t=0;t<=2;t++){
						if(s==t && i) continue;
						if(st[i+1]=='?' || st[i+1]==t+'a'){
							ll J = j, K = k;
							if(t==0) J++; if(t==1) K++;
							addmod(f[t][i+1][J][K] += f[s][i][j][k]);
						}
					}
				}
			}
		}
	}
	for(int j=0;j<=n;j++) for(int k=0;j+k<=n;k++)
		for(int s=0;s<=2;s++){
			addmod(g[j][k][n-j-k] += f[s][n][j][k]);
		}

	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++) addmod(g[i][j][k] += g[i-1][j][k]);
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<=n;k++) addmod(g[i][j][k] += g[i][j-1][k]);
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int k=1;k<=n;k++) addmod(g[i][j][k] += g[i][j][k-1]);
		}
	}
	while(q--){
		int A=min(n, (int)read()+a), B=min(n, (int)read()+b), C=min(n, (int)read()+c);
		printf("%d\n", g[A][B][C]);
	}
}
int main(){
	#ifdef LOCAL
		assert(freopen("input.txt","r",stdin));
		assert(freopen("output.txt","w",stdout));
	#endif
	ll T=1;
	init();
	while(T--) procedure();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8108kb

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: 1ms
memory: 8032kb

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: 7956kb

input:

1 1
?
0 1 1

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 1ms
memory: 8156kb

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: 1ms
memory: 8220kb

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: 0ms
memory: 11180kb

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: 4ms
memory: 12192kb

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: 3ms
memory: 20528kb

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: 10ms
memory: 29156kb

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:

804458366
986514507
631676168
668774326
10104
806873682
457652893
556612659
833031739
194151457
769278037
274041326
594216165
183174115
939173449
604062764
737118944
281846238
379026979
660541372
959207727
575057371
385668393
989871351
166230586
907706324
523034330
586950612
67939963
816607907
42635...

result:

wrong answer 1st lines differ - expected: '490475656', found: '804458366'
English 繁體中文 简体中文

Server Time: 2025-02-07 23:05:05 | OpenSource Project