QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#690392 | #9442. Music Game | TJ_Andeviking | WA | 21ms | 4180kb | C++20 | 1.3kb | 2024-10-30 21:58:40 | 2024-10-30 21:58:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define range(x) (x).begin(), (x).end()
const int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};
const ll mod = 998244353;
ll qpow(ll a, ll b)
{
ll ans = 1;
a %= mod;
for (; b; b >>= 1) {
if (b & 1)
ans = ans * a % mod;
a = a * a % mod;
}
return ans % mod;
}
void solve()
{
int n;
cin >> n;
vector<int> a(n + 5), b(n + 5), t(n + 5);
for (int i = 1; i <= n; ++i) {
cin >> t[i] >> a[i] >> b[i];
}
vector<int> v;
for (int i = 1; i <= n; ++i)
v.push_back(i);
sort(range(v), [&](const auto &i, const auto &j) {
return 1ll * t[i] * b[i] * (b[j] - a[j]) < 1ll * t[j] * b[j] * (b[i] - a[i]);
});
ll ans = 0;
ll tag = 1;
ll sum = 0;
for (int i = 1; i <= n; ++i) {
int idx = v[i - 1];
sum += t[idx];
ll p = 1ll * a[idx] * qpow(b[idx], mod - 2) % mod;
// cout << idx << '\n';
(ans += tag * (mod - p + 1) % mod * sum % mod) %= mod;
(tag *= p) %= mod;
}
(ans += tag * sum) %= mod;
(ans *= qpow(tag, mod - 2)) %= mod;
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
2 3 3 5 2 4 7
output:
831870305
result:
ok "831870305"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3772kb
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: 0ms
memory: 3608kb
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: 0ms
memory: 3652kb
input:
2 2 2 3 1 5 6
output:
399297746
result:
ok "399297746"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3980kb
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: 21ms
memory: 4180kb
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:
927450136
result:
wrong answer 1st words differ - expected: '401590376', found: '927450136'