QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#613614 | #9442. Music Game | ucup-team4938# | WA | 16ms | 8372kb | C++14 | 1.6kb | 2024-10-05 14:20:08 | 2024-10-05 14:20:57 |
Judging History
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'