QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#631287#9442. Music Gamereal_sigma_team#WA 1ms3840kbC++231.6kb2024-10-11 23:47:352024-10-11 23:47:36

Judging History

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

  • [2024-10-11 23:47:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2024-10-11 23:47:35]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

void solve();

bool comp(const tuple<ll, ll, ll>& a, const tuple<ll, ll, ll>& b) {
	return get<0>(a) * get<1>(a) * get<2>(b) < get<0>(b) * get<1>(b) * get<2>(a);
}

constexpr int mod = 998244353;

ll add(ll a, ll b) {
	return a + b >= mod ? a + b - mod : a + b;
}

ll sub(ll a, ll b) {
	return a >= b ? a - b : a - b + mod;
}

ll mul(ll a, ll b) {
	return a * b % mod;
}

ll bin_pow(ll a, ll x) {
	ll res = 1;
	while (x) {
		if (x & 1) {
			res = mul(res, a);
		}
		a = mul(a, a);
		x >>= 1;
	}
	return res;
}

ll inv(ll a) {
	return bin_pow(a, mod - 2);
}

int32_t main() {
	int n;
	cin >> n;
	vector<ll> t(n), a(n), b(n);
	vector<tuple<ll, ll, ll>> ar(n);
	for (int i = 0; i < n; i++) {
		cin >> t[i];
		cin >> a[i] >> b[i];
		a[i] = b[i] - a[i];
		ar[i] = {t[i], a[i], b[i]};
	}
	sort(ar.begin(), ar.end(), comp);
	for (int i = 0; i < n; i++) {
		t[i] = get<0>(ar[i]);
		a[i] = get<1>(ar[i]);
		b[i] = get<2>(ar[i]);
	}
	vector<ll> prob(n + 1), pref(n + 1);
	prob[0] = mul(a[0], inv(b[0]));
	pref[0] = t[0];
	ll pr = mul(b[0] - a[0], inv(b[0]));
	for (int i = 1; i < n; i++) {
		prob[i] = mul(pr, mul(a[i], inv(b[i])));
		pref[i] = add(pref[i - 1], t[i]);
		pr = mul(pr, mul(b[i] - a[i], inv(b[i])));
	}
	prob[n] = pr;
	pref[n] = pref[n - 1];
	ll e = 0;
	for (int i = 0; i < n; i++) {
		e = add(e, mul(prob[i], pref[i]));
	}
	if (pr == 1) {
		cout << pref[n] << '\n';
		return 0;
	}
	// e = mul(e, inv(sub(1, pr)));
	cout << add(pref[n], mul(e, inv(pr))) << '\n';
}

詳細信息

Test #1:

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

input:

2
3 3 5
2 4 7

output:

831870305

result:

ok "831870305"

Test #2:

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

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: -100
Wrong Answer
time: 0ms
memory: 3704kb

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:

273043002

result:

wrong answer 1st words differ - expected: '923892723', found: '273043002'