QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#119152 | #5505. Great Chase | hos_lyric | AC ✓ | 968ms | 9456kb | C++14 | 2.1kb | 2023-07-05 01:53:38 | 2023-07-05 01:53:41 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
using Double = long double;
constexpr Double INF = 1e+30;
int N;
Int U;
vector<Int> P, V;
int main() {
for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
scanf("%d%lld", &N, &U);
P.resize(N);
V.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld%lld", &P[i], &V[i]);
}
Double lo = 0.0, hi = 1e+15;
for (int iter = 0; iter < 100; ++iter) {
const Double mid = (lo + hi) / 2;
Double mxL = -INF;
Double mnR = +INF;
for (int i = 0; i < N; ++i) {
if (P[i] < 0) {
chmax(mxL, P[i] + V[i] * mid);
} else {
chmin(mnR, P[i] - V[i] * mid);
}
}
((mxL >= mnR) ? hi : lo) = mid;
}
const Double ans = U * hi;
printf("%.12Lf\n", ans);
}
#ifndef LOCAL
break;
#endif
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
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.250000000000 1.230769230769 3000000000000.000000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 575ms
memory: 3712kb
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.349110037088 16414958969.727281192318 5202715639.835183900315 321977234.156325869262 45384199210.221683971584 183885744.769230769234 1708925225.230472358060 89786664971.557942636311 13924365606.287388795055 412975327.555555555708 965508404.512101492670 4703493416.288376524579 352961619....
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 897ms
memory: 4112kb
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.363636363705 197971181.333333333387 997533531.737629592477 6439673170.665741784964 993821598110.661077857018 22727977326.402660988271 34702455207.518504031003 677770533.929817498836 46631726883.969133235514 5446481867.129032258410 11336247450.272078594193 4409370840.439131625928 1568160605...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 855ms
memory: 9456kb
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.811770915985 511413015796.766475379467 424240880533.634020328522 518849481155.503918796778 1882496988186.444000005722
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 968ms
memory: 7848kb
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.978608019650 98630840901.507606960833 29393530999.894327789545 50801000770.955985423177 39668001027.269331343472 467846478226.411370843649 30789914370.574311614037 23151476830.905098434538 51606123416.625827591866 151713060001.662588924170 100944679009.609286278486 766785664078.358981728...
result:
ok 38 numbers