QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84363 | #5505. Great Chase | blockche | WA | 543ms | 3532kb | C++20 | 1.2kb | 2023-03-06 12:10:18 | 2023-03-06 12:11:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n, w;
cin >> n >> w;
vector<pair<i64, i64>> a, b;
for (int i = 0; i < n; i++) {
i64 p, v;
cin >> p >> v;
if (p < 0) {
a.emplace_back(p, v);
} else {
b.emplace_back(p, v);
}
}
sort(a.begin(), a.end(), greater());
sort(b.begin(), b.end());
double lo = 0, hi = 3e12;
for (int i = 0; i < 70; i++) {
double mid = (lo + hi) / 2;
double l = -1e18, r = 1e18;
for (auto [p, v] : a) {
l = max(l, mid * v + p);
}
for (auto [p, v] : b) {
r = min(r, -mid * v + p);
}
if (l < r) {
lo = mid;
} else {
hi = mid;
}
}
double ans = lo * w;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << setprecision(15) << fixed;
int T;
cin >> T;
while (T--) {
solve();
}
// double a = 2999999999999.999511718750000, b = 3000000000000;
// double t = abs(a - b) / max(1.0, b);
// cerr << t << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3532kb
input:
3 4 9 10 2 -7 2 -6 1 7 1 2 8 -1 7 1 6 2 3 -1000000000000 1 1000000000000 1
output:
38.249999999626475 1.230769230021328 2999999999999.999511718750000
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 543ms
memory: 3508kb
input:
10000 200 997007 405524182320 754760 686939601648 419804 687047488212 715566 1446157132 4594 -670522037 4673 763634629282 253755 424307411732 275041 1582708381 8473 -667425982 4622 -522841486 1427 702430907988 460271 1405423646 1060 1497754648 6227 883363410675 723547 56899800372 46435 -810216390 64...
output:
145405766328.348022460937500 16414958969.727172851562500 5202715639.835094451904297 321977234.154489994049072 45384199210.220291137695312 183885744.769206404685974 1708925225.229010105133057 89786664971.557067871093750 13924365606.286529541015625 412975327.555292487144470 965508404.511069893836975 4...
result:
wrong answer 4566th numbers differ - expected: '1.0000010', found: '0.9986518', error = '0.0013492'