QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#474459 | #5505. Great Chase | piratZnachor# | AC ✓ | 1362ms | 19060kb | C++14 | 3.6kb | 2024-07-12 18:39:39 | 2024-07-12 18:39:39 |
Judging History
answer
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// #define int long long
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define pb push_back
#define BOOST ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
void test_case() {
int n;
ll vr;
cin >> n >> vr;
vector<pair<ll,ll>> left, right;
for(int i = 0; i < n; i++) {
ll x, v;
cin >> x >> v;
if(x < 0) left.pb({x, v});
else right.pb({x, v});
}
auto check = [&](ld x) {
ld left_max = -1e13, right_min = 1e13;
for(auto p : left) {
left_max = max(left_max, p.first + p.second * x);
}
for(auto p : right) {
right_min = min(right_min, p.first - p.second * x);
}
return left_max > right_min;
};
ld l = 0, r = 1e12 + 5;
for(int i = 0; i < 200; i++) {
ld mid = (l + r) / 2;
if(check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << fixed << setprecision(12) << vr * l << "\n";
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tc = 1;
cin >> tc;
while(tc--) {
test_case();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
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: 1134ms
memory: 3956kb
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.727281190455 5202715639.835183899850 321977234.156325868942 45384199210.221683971584 183885744.769230769234 1708925225.230472357944 89786664971.557942636311 13924365606.287388794124 412975327.555555555533 965508404.512101492495 4703493416.288376523647 352961619....
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 1362ms
memory: 4272kb
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.363636363632 197971181.333333333328 997533531.737629592360 6439673170.665741784498 993821598110.661077797413 22727977326.402660986409 34702455207.518504027277 677770533.929817498662 46631726883.969133231789 5446481867.129032257944 11336247450.272078594193 4409370840.439131624997 1568160605...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 1359ms
memory: 19060kb
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.811770886183 511413015796.766475349665 424240880533.634020358324 518849481155.503918766975 1882496988186.443999886513
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 1357ms
memory: 8820kb
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.978608012199 98630840901.507606953382 29393530999.894327787682 50801000770.955985419452 39668001027.269331343472 467846478226.411370813847 30789914370.574311612174 23151476830.905098432675 51606123416.625827591866 151713060001.662588909268 100944679009.609286278486 766785664078.358981668...
result:
ok 38 numbers