QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#270357 | #5505. Great Chase | pooty# | AC ✓ | 544ms | 18316kb | C++14 | 1.6kb | 2023-11-30 19:44:44 | 2023-11-30 19:44:45 |
Judging History
answer
#ifdef MY_LOCAL
#include "D://competitive_programming/debug/debug.h"
#define debug(x) cerr << "[" << #x<< "]:"<<x<<"\n"
#else
#define debug(x)
#endif
#define REP(i, n) for(int i = 0; i < (n); i ++)
#define REPL(i,m, n) for(int i = (m); i < (n); i ++)
#define SORT(arr) sort(arr.begin(), arr.end())
#define LSOne(S) ((S)&-(S))
#define sz(X) ((int)X.size())
#define READ(arr) for(auto &a: arr){cin>>a;}
#define SUM(arr) accumulate((arr).begin(), (arr).end(), 0LL)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef tree<int,null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
const ll INF = 1e18;
#define double long double
void solve() {
int n,v;cin>>n>>v;
vii arr1;
vii arr2;
REP(i, n) {
int p,vv;cin>>p>>vv;
if (p < 0) {
arr1.push_back({-p, vv});
} else {
arr2.push_back({p, vv});
}
}
double EPS = 1e-9;
double mn = 0;
double mx = 1e13;
while (mx - mn > EPS*mn) {
double md = (mx + mn)/2;
double b1 = -INF;
double b2 = -INF;
for (auto [x,y]: arr1) {
b1 = max(b1, y*md - x);
}
for (auto [x,y]: arr2) {
b2 = max(b2, y*md - x);
}
if (b1 + b2 >= 0) {
mx = md;
} else {
mn = md;
}
}
cout<<setprecision(13)<<mn*v<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin>>tc;
REP(i, tc) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3720kb
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.24999997676 1.230769230021 2999999999302
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 477ms
memory: 3628kb
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:
145405766227.3 16414958965.86 5202715637.36 321977233.9482 45384199201.35 183885744.7673 1708925224.32 89786664912.58 13924365599 412975327.3641 965508403.7355 4703493413.333 352961619.3039 5575125770.494 341191686.8917 985544508.0442 1370541507.122 143194575.0321 8728055563.922 28694043960.44 13681...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 544ms
memory: 4240kb
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.2737 197971181.235 997533531.6964 6439673168.998 993821598079.4 22727977324.25 34702455205.44 677770533.8543 46631726863.65 5446481865.254 11336247447.03 4409370839.609 15681606045.47 14986614228.18 1025909752.306 18994454575.72 105092139089.7 25758936823.53 252231500.6933 50720505852.35 4...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 528ms
memory: 18316kb
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:
519985220185.8 511413015696 424240880484.4 518849481058.7 1882496987695
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 524ms
memory: 8720kb
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:
89670748251.1 98630840899.84 29393530989.03 50801000767.15 39668001002.02 467846477970.2 30789914357.47 23151476823.11 51606123402.42 151713059913.7 100944678977.4 766785663898.4 39969642777.64 62341065910.64 323981604123 115228654959.8 52894567545.31 83882295605.06 20963769165.67 117523885615.8 373...
result:
ok 38 numbers