QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690392#9442. Music GameTJ_AndevikingWA 21ms4180kbC++201.3kb2024-10-30 21:58:402024-10-30 21:58:41

Judging History

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

  • [2024-10-30 21:58:41]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:4180kb
  • [2024-10-30 21:58:40]
  • 提交

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'