QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618643 | #9442. Music Game | APROHACK124 | WA | 0ms | 7664kb | C++14 | 1.9kb | 2024-10-07 01:49:21 | 2024-10-07 01:49:22 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using ll = long long;
using lf = long double;
using namespace std;
int n;
const int mod = 998244353;
ll multi(ll a, ll b){
return a * b % mod;
}
ll sume(ll a, ll b){
return (a + b) % mod;
}
ll fast_expo(ll base, ll exp){
if(exp == 0)return 1;
ll temp = fast_expo(base, exp / 2);
if(exp % 2 == 0)return temp * temp % mod;
return temp * temp % mod * base % mod;
}
ll mod_inv(ll k){
return fast_expo(k, mod - 2);
}
ll t[200005], p[200005], q[200005];
vector<pair<pair<ll, ll>, ll > > v;
ll expected(ll qq, ll pp){
return multi(qq, mod_inv(multi(pp,pp)));
}
bool cmp(pair<pair<ll, ll>, ll>a, pair<pair<ll, ll>, ll> b){
// a < b if
ll mul1 = a.ff.ff * b.ff.ss;
ll mul2 = a.ff.ss * b.ff.ff;
if( mul1 < mul2 )return true;
if(mul1 > mul2)return false;
return a.ss < b.ss;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
cin >> n;
for(int i = 0 ; i < n ; i++){
ll a, b;
cin >> t[i] >> a >> b;
p[i] = a * mod_inv(b) % mod;
q[i] = (b - a) * mod_inv(b) % mod;
v.pb({{a, b}, t[i]});
}
sort(v.begin(), v.end(), cmp);
for(int i = 0 ; i < n ; i ++){
ll a = v[i].ff.ff;
ll b = v[i].ff.ss;
p[i] = a * mod_inv(b) % mod;
q[i] = (b - a) * mod_inv(b) % mod;
t[i] = v[i].ss;
}
ll ans = 0;
ll tempo = 0;
ll acum = 1;
for(int i = 0 ; i < n ; i ++){
acum = multi(acum, p[i]);
tempo = sume(t[i], tempo);
ans = sume(ans, multi(tempo, expected(q[i], p[i])));
}
ans = sume(ans, multi(tempo, acum));
if(ans < 0)ans += mod;
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7664kb
input:
2 3 3 5 2 4 7
output:
881386393
result:
wrong answer 1st words differ - expected: '831870305', found: '881386393'