QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87349 | #5505. Great Chase | chiranko# | TL | 15ms | 8976kb | Python3 | 816b | 2023-03-12 17:49:07 | 2023-03-12 17:49:10 |
Judging History
answer
import decimal
from decimal import *
decimal.getcontext().prec=30
cases = int(input())
for _ in range(cases):
n, vv = input().split()
n = int(n)
vv = Decimal(vv)
p = [0 for _ in range(n)]
v = [0 for _ in range(n)]
for i in range(n):
p[i], v[i] = map(Decimal, input().split())
l, r = Decimal(0.0), Decimal(2e12)
while r - l > 1e-12:
mid = (l + r) / 2
maxl, minr = Decimal(-1e12-1), Decimal(1e12+1)
for i in range(n):
if p[i] < 0:
maxl = max(maxl, p[i] + mid * v[i])
else:
minr = min(minr, p[i] - mid * v[i])
if maxl > minr:
r = mid
else:
l = mid
res = vv * l
print(res.quantize(Decimal("1.000000000000")))
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 8976kb
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 3000000000000.000000000000
result:
ok 3 numbers
Test #2:
score: -100
Time Limit Exceeded
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.349109325608 16414958969.727280460716 5202715639.835183573441 321977234.156325340786 45384199210.221683415549 183885744.769230752421 1708925225.230472021448 89786664971.557942005040 13924365606.287388203685 412975327.555555497289 965508404.512101212859 4703493416.288376164304 352961619....