QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87346 | #5505. Great Chase | chiranko# | WA | 852ms | 3760kb | C++14 | 1.0kb | 2023-03-12 17:19:27 | 2023-03-12 17:19:30 |
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-8;
int n;
LDB v;
cin >> n >> v;
vector<DB> pos(n + 1, 0), speed(n + 1, 0);
for(int i = 1; i <= n; ++i){
cin >> pos[i] >> speed[i];
}
LDB l = 0.0, r = 2e12, mid = 0, round = 0;
while(fabs(r - l) > eps && round <= 1000){
++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;
cin >> T;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3572kb
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.249999969133 1.230769230021 2999999999999.999999761581
result:
ok 3 numbers
Test #2:
score: -100
Wrong Answer
time: 852ms
memory: 3760kb
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.343816384673 16414958969.723367564380 5202715639.832895367872 321977234.151215863094 45384199210.218583468348 183885744.769183206765 1708925225.223952701548 89786664971.557044439018 13924365606.286528770812 412975327.554778008634 965508404.508872970880 4703493416.283940238412 352961619....
result:
wrong answer 4566th numbers differ - expected: '1.0000010', found: '0.9961107', error = '0.0038903'