QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139516 | #5505. Great Chase | ammardab3an# | WA | 355ms | 3784kb | C++17 | 1.0kb | 2023-08-13 19:43:14 | 2023-08-13 19:43:16 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 1e6 + 10, MM = 1e9 + 7, MAX = 1e18;
int solve() {
int n; cin >> n;
ll v; cin >> v;
vector<pair<ll, ll>>lef, rig;
for (int i = 0; i < n; i++) {
ll a, b; cin >> a >> b;
if (a < 0) {
lef.emplace_back(a, b);
}
else {
rig.emplace_back(a, b);
}
}
double l = 0, r = 1e18;
double time = 0;
int num = 100;
while (abs(r - l) > 1e-9&&num) {
double mid = l + (r - l) / 2.0;
double mxlef = -MAX, mnrig = MAX;
for (auto x : lef) {
mxlef = max(mxlef, mid * x.second + x.first);
}
for (auto x : rig) {
mnrig = min(mnrig, x.first - mid * x.second);
}
if (mnrig <= mxlef) {
time = mid;
r = mid;
}
else {
l = mid;
}
num--;
}
printf("%.10f\n", time * v);
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
int i = 1;
while (t--) {
//cout << "case " << i << ": ";
solve();
}
return 0;
}
/*
204
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
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.2500000003 1.2307692325 3000000000000.0000000000
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 355ms
memory: 3784kb
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.3494873047 16414958969.7277622223 5202715639.8355846405 321977234.1563583016 45384199210.2218246460 183885744.7692473531 1708925225.2309525013 89786664971.5586242676 13924365606.2879676819 412975327.5556929708 965508404.5124481916 4703493416.2883796692 352961619.3818355799 5575125771.79...
result:
wrong answer 4566th numbers differ - expected: '1.0000010', found: '1.0000484', error = '0.0000474'