QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#507206 | #5505. Great Chase | NYCU_MyGO# | AC ✓ | 493ms | 19476kb | C++20 | 5.8kb | 2024-08-06 13:39:04 | 2024-08-06 13:39:04 |
Judging History
answer
#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO
const double INF = 1e13;
void solve() {
int N; cin >> N;
double V; cin >> V;
vector<pii> cops_l, cops_r;
for (int i = 0; i < N; ++i) {
int p, v; cin >> p >> v;
if (p < 0) cops_l.eb(-p, v);
if (p > 0) cops_r.eb( p, v);
}
sort(ALL(cops_l)), sort(ALL(cops_r));
double ans = 0.0;
double lo = -cops_l[0].first, hi = cops_r[0].first, mi;
for (int _round = 1; _round <= 50; ++_round) {
mi = (lo + hi) / 2.0;
double min_time_l = INF, min_time_r = INF;
for (auto [p, v] : cops_l) chmin(min_time_l, (p + mi) / v);
for (auto [p, v] : cops_r) chmin(min_time_r, (p - mi) / v);
ans = V * min_time_l;
if (min_time_l > min_time_r) hi = mi;
else lo = mi;
}
cout << fixed << setprecision(15) << ans << "\n";
}
int32_t main() {
fastIO();
int t = 1; cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
fprintf(stderr, "\u001b[33m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
#endif
/*
iiiiii iiiiiiiiii iiiiiiiiiiiiii
iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
iiiii iiiiii iiii iiiii iii ii ii i
iiiiii iiiiiiii iiiii iiiii ii ii ii
iiiii iiii iiii iiiiiiiiiiii ii
iii iiii iiii iiiiiiii
iiiii iiii
iiii iiii
iiii iiiii
iii iiiii
iii iiiii
iii iiiiii
iiiiiiiii
iiiiii
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
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.250000000000028 1.230769230769232 3000000000000.005371093750000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 367ms
memory: 3940kb
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.349060058593750 16414958969.727273941040039 5202715639.835216522216797 321977234.156325340270996 45384199210.221733093261719 183885744.769230872392654 1708925225.230470418930054 89786664971.557937622070312 13924365606.287395477294922 412975327.555555462837219 965508404.512101411819458 4...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 455ms
memory: 4312kb
input:
93 15435 968117 4196666 184 -5069875 255 -9782648 980 -1978138 176 9333323 764 -4323540 12 -8442049 319 -5371878 137 2881306 10 -4050629 133 -4659099 59 -5189169 320 -2256647 99 -3686648 37 1059255 33 -223142 20 8040933 408 8407764 705 694547 38 -7913614 746 -3573355 132 5919585 189 -3756662 94 -795...
output:
189662921.363637089729309 197971181.333333522081375 997533531.737629532814026 6439673170.665739059448242 993821598110.661132812500000 22727977326.402664184570312 34702455207.518470764160156 677770533.929817557334900 46631726883.969131469726562 5446481867.129054069519043 11336247450.272098541259766 4...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 493ms
memory: 19476kb
input:
5 400000 999972 172811492468 106699 171900177092 102097 194121748377 184014 190302947556 172722 183121572232 149212 196566712700 190884 171376795991 99358 522927044000 159597 -129031052077 34395 189422320931 170012 -275879974024 638546 408864707565 98475 -106703244806 368801 192128798630 178213 2915...
output:
519985220219.812072753906250 511413015796.766235351562500 424240880533.634277343750000 518849481155.503601074218750 1882496988186.444091796875000
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 469ms
memory: 8788kb
input:
38 16668 999947 -3844782803 511 -210897941456 464872 618726004990 714384 -954596898686 225256 96675744 1148 -1515974078 11375 -206213840984 706184 306078847 3947 -474818331950 391451 -616022698917 561244 123378707 1540 -640636592655 406006 459201391325 908506 -733249583 5719 496163273 6238 619876911...
output:
89670748252.978500366210938 98630840901.507675170898438 29393530999.894336700439453 50801000770.955986022949219 39668001027.269332885742188 467846478226.411437988281250 30789914370.571952819824219 23151476830.905101776123047 51606123416.625823974609375 151713060001.662597656250000 100944679009.60929...
result:
ok 38 numbers