QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87353 | #5505. Great Chase | chiranko# | WA | 840ms | 3712kb | C++14 | 1.0kb | 2023-03-12 18:06:58 | 2023-03-12 18:07:02 |
Judging History
answer
#include <bits/stdc++.h>
#define pb emplace_back
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;
using LDB = long double;
using DB = double;
using LL = long long;
void solve()
{
LDB eps = 1e-12;
int n;
LDB v;
scanf("%d%Lf", &n, &v);
vector<LDB> pos(n + 1, 0), speed(n + 1, 0);
for(int i = 1; i <= n; ++i){
scanf("%Lf%Lf", &pos[i], &speed[i]);
}
LDB l = 0.0, r = 1e12, mid = 0, round = 0;
while(fabs(r - l) > eps && round <= 200){
++round;
mid = (l + r) / 2;
LDB maxl = -1e12 - 1, minr = 1e12 + 1;
for(int i = 1; i <= n; ++i){
if(pos[i] < 0)
maxl = max(maxl, pos[i] + mid * speed[i]);
else
minr = min(minr, pos[i] - mid * speed[i]);
}
if(maxl >= minr)
r = mid;
else
l = mid;
// printf("%.12Lf %.12Lf %.12Lf %.12Lf %.12Lf %.12Lf\n",maxl, minr, l, r, mid, (l + r) / 2);
}
printf("%.12Lf\n", l * v);
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);
int T;
scanf("%d", &T);
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
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.249999999999 1.230769230769 2999999999999.999999761581
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 840ms
memory: 3704kb
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.349109321833 16414958969.727280461229 5202715639.835183573887 321977234.156325340795 45384199210.221683416516 183885744.769230752412 1708925225.230472021620 89786664971.557942003012 13924365606.287388203666 412975327.555555497267 965508404.512101212866 4703493416.288376164623 352961619....
result:
wrong answer 4566th numbers differ - expected: '1.0000010', found: '1.0000010', error = '0.0000000'