QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#613614#9442. Music Gameucup-team4938#WA 16ms8372kbC++141.6kb2024-10-05 14:20:082024-10-05 14:20:57

Judging History

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

  • [2024-10-05 14:20:57]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:8372kb
  • [2024-10-05 14:20:08]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int 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<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,ans;
struct nd{
	int t,a,b,p;
}a[maxn];
inline int ksm(int a,int b=mod-2){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int val[maxn],t[maxn];
void work(){
	n=read();
	for(int i=1;i<=n;i++)a[i]={read(),read(),read(),0},a[i].p=a[i].a*ksm(a[i].b)%mod;
	sort(a+1,a+n+1,[&](nd u,nd v){return (u.t*(u.b-u.a)+(u.t+v.t)*u.a)*v.b<(v.t*(v.b-v.a)+(u.t+v.t)*v.a)*u.b;});
	// sort(a+1,a+n+1,[&](nd u,nd v){return u.a*v.b<v.a*u.b;});
	// sort(a+1,a+n+1,[&](nd u,nd v){return u.t<v.t;});
	// for(int i=1;i<=n;i++)cout<<a[i].t<<" "<<a[i].a<<" "<<a[i].b<<"\n";
	val[0]=1;for(int i=1;i<=n;i++)val[i]=val[i-1]*a[i].p%mod;
	for(int i=1;i<=n;i++)t[i]=t[i-1]+a[i].t;
	int num=ksm(val[n]);
	// cout<<num<<"\n";
	for(int i=0;i<n;i++)(ans+=t[i+1]*num%mod*(val[i]*(1+mod-a[i+1].p)%mod))%=mod;
	(ans+=t[n])%=mod;
	printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7828kb

input:

2
3 3 5
2 4 7

output:

831870305

result:

ok "831870305"

Test #2:

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

input:

5
2 5 9
6 4 7
1 9 14
17 8 13
10 4 11

output:

914017655

result:

ok "914017655"

Test #3:

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

input:

8
6 2 8
3 1 8
5 30 71
7 9 58
6 4 7
6 9 25
2 8 67
6 6 55

output:

923892723

result:

ok "923892723"

Test #4:

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

input:

2
2 2 3
1 5 6

output:

399297746

result:

ok "399297746"

Test #5:

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

input:

6057
598846 477861 477861
355457 471360 471360
52553 53505 53505
910434 715394 957062
829770 396343 396343
388604 220815 628584
697515 339144 976739
134698 713562 713562
103516 548592 976096
328488 131879 979654
360558 458803 458803
609012 481090 852195
207954 434215 434215
74492 313219 453266
11312...

output:

209793398

result:

ok "209793398"

Test #6:

score: -100
Wrong Answer
time: 16ms
memory: 8372kb

input:

60325
249263 702771 806647
825858 894224 894224
954851 857512 857512
682622 271953 271953
37366 859065 859065
455311 280629 280629
139413 628817 628817
289777 745827 889101
941889 44512 44512
261500 956143 956143
683456 849819 849819
380838 640198 640198
458670 425331 923542
724423 786203 786203
886...

output:

950063516

result:

wrong answer 1st words differ - expected: '401590376', found: '950063516'