QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133840#4939. Red Black Ballsalvator_nosterWA 4ms120140kbC++142.4kb2023-08-02 15:13:442023-08-02 15:13:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 15:13:45]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:120140kb
  • [2023-08-02 15:13:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;


#define rep(i,a,b) for(ll i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(ll i=a,i##end=b;i>=i##end;--i)

#define erep(i,a) for(ll i=hd[a],y;(y=to[i]);i=nxt[i])
#define Mod(x) (x>=P)&&(x-=P)
typedef long long ll;
char IO;
ll rd(ll res=0){
	bool f=0;
	while(IO=getchar(),IO<48||IO>57)
		f|=IO=='-';
	do res=(res<<1)+(res<<3)+(IO^48);
	while(isdigit(IO=getchar()));
	return f?-res:res;
}
void Max(ll &x,ll y){x<y&&(x=y);}
const ll M=155,P=998244353;
ll n,dp[M][M][M*2][2],C[M][M],ans[M*2][2],m;

struct node{
	ll x,c;
	bool operator <(const node &_)const{
		return x<_.x;
	}
}p[M];
ll dfs(ll l,ll r,ll cl,ll dis){
	if(l==r-1){
		return dis==0;
	}
	if(dis+n<0)return 0;
	if(~dp[l][r][dis+n][cl])return dp[l][r][dis+n][cl];
	ll res=0;
	rep(k,l+1,r-1){
		if(p[k].x-p[l].x<=p[r].x-p[k].x){
			if(cl)res+=dfs(k,r,cl,dis-(k-l))*C[r-l-2][r-k-1]%P,Mod(res);
			else res+=dfs(k,r,cl,dis+(k-l))*C[r-l-2][r-k-1]%P,Mod(res);
		}else{
			if(!cl)res+=dfs(l,k,cl,dis-(r-k))*C[r-l-2][r-k-1]%P,Mod(res);
			else res+=dfs(l,k,cl,dis+(r-k))*C[r-l-2][r-k-1]%P,Mod(res);
		}
	}
	return dp[l][r][dis+n][cl]=res;
}
char s[10];
int fac[M];
int main(){
	memset(dp,-1,sizeof dp);
	n=rd(),m=rd();
	rep(i,1,n){
		p[i].x=rd();
		scanf("%s",s);
		if(*s=='B')p[i].c=2;
		else p[i].c=1;
	}
	rep(i,1,m)p[i+n].x=rd();
	n+=m;
	rep(i,fac[0]=1,n)fac[i]=fac[i-1]*i%P;
	sort(p+1,p+n+1);
	rep(i,0,n)rep(j,C[i][0]=1,i)
		C[i][j]=C[i-1][j]+C[i-1][j-1],Mod(C[i][j]);
	ll L,R;
	rep(i,1,n)if(p[i].c)R=i;
	drep(i,n,1)if(p[i].c)L=i;

	ll t=0,cnt=0;
	if(p[L].c==1)t+=L-1;
	else t-=L-1;
	if(p[R].c==1)t+=n-R;
	else t-=n-R;
	cnt=L-1+n-R;
	rep(i,1,n)t+=(p[i].c==1)-(p[i].c==2);
	ans[t+n][0]=fac[n-R]*fac[L-1]%P*C[L-1+n-R][L-1]%P;
	ll tl=L;
	rep(i,L+1,n){
		if(p[i].c){
			cnt+=i-tl-1;
			if(p[i].c==p[tl].c){
				if(p[i].c==2){
					rep(j,-n,n)if(j-(i-tl-1)+n>=0)
						ans[j-(i-tl-1)+n][1]+=ans[j+n][0]*C[cnt][i-tl-1]%P*fac[i-tl-1]%P,Mod(ans[j-(i-tl-1)+n][1]);
				}else{
					rep(j,-n,n)
						ans[j+(i-tl-1)+n][1]+=ans[j+n][0]*C[cnt][i-tl-1]%P*fac[i-tl-1]%P,Mod(ans[j+(i-tl-1)+n][1]);
				}
			}else{
				rep(j,-n,n)rep(k,-n,n)if(j+k+n>=0)
					ans[j+k+n][1]+=ans[j+n][0]*dfs(tl,i,2-p[tl].c,k)%P*C[cnt][i-tl-1]%P,Mod(ans[j+k+n][1]);
			}
			tl=i;
			rep(j,-n,n)ans[j+n][0]=ans[j+n][1],ans[j+n][1]=0;
		}
	}
	ll res=0;
	rep(i,1,n)res+=ans[i+n][0],Mod(res);
	printf("%lld",res);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 120020kb

input:

2 3
1 BLACK
10 RED
2 5 7

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 3ms
memory: 120064kb

input:

2 3
1 RED
10 BLACK
2 4 7

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 4ms
memory: 120052kb

input:

2 3
1 RED
10 BLACK
7 4 2

output:

6

result:

ok single line: '6'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 120140kb

input:

20 46
238846592 BLACK
199923217 RED
526626128 BLACK
62308338 RED
523811748 RED
59432 BLACK
273113193 BLACK
730729301 BLACK
973259012 RED
225318015 BLACK
611574923 RED
234880345 RED
485448383 BLACK
405607946 BLACK
747693124 RED
794086621 BLACK
91585417 BLACK
466451303 RED
244184598 RED
334788273 RED
...

output:

748106537

result:

wrong answer 1st lines differ - expected: '850819974', found: '748106537'