QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#76947 | #5505. Great Chase | CrazyMurky# | AC ✓ | 1284ms | 33016kb | C++20 | 4.4kb | 2023-02-12 19:09:35 | 2023-02-12 19:09:36 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimization("O3")
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <iomanip>
#include <algorithm>
#include <iterator>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <numeric>
#include <deque>
#include <list>
#include <bitset>
#include <array>
#include <tuple>
#include <sstream>
#include <functional>
#include <cmath>
#include <random>
#include <cstring>
#include <fstream>
#include <stdexcept>
using namespace std;
#define pb push_back
#define mp make_pair
#define ifor(a, b) for(int i = a; i < b; ++i)
#define jfor(a, b) for(int j = a; j < b; ++j)
#define kfor(a, b) for(int k = a; k < b; ++k)
#define irof(a, b) for(int i = b - 1; i >= a; --i)
#define jrof(a, b) for(int j = b - 1; j >= a; --j)
#define krof(a, b) for(int k = b - 1; k >= a; --k)
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const ll MOD = 998244353;
ll mmod(ll x, ll y = MOD) {
if (x >= 0)
return x % y;
return (y - ((-x) % y)) % y;
}
template <ll T = MOD>
struct Res {
ll value;
Res() : value(0) {}
Res(ll val) : value(mmod(val, T)) {}
Res& operator=(ll val) {
value = mmod(val, T);
return *this;
}
Res operator+(const Res<T>& other) const {
return Res(mmod(value + other.value, T));
}
Res operator-(const Res<T>& other) const {
return Res(mmod(value - other.value, T));
}
Res operator*(const Res<T>& other) const {
return Res(mmod(value * other.value, T));
}
Res operator+(const Res<T>&& other) const {
return Res(mmod(value + other.value, T));
}
void operator+=(const Res<T>& other) {
value = mmod(value + other.value, T);
}
void operator-=(const Res<T>& other) {
value = mmod(value - other.value, T);
}
void operator*=(const Res<T>& other) {
value = mmod(value * other.value, T);
}
Res operator-(const Res<T>&& other) const {
return Res(mmod(value - other.value, T));
}
Res operator*(const Res<T>&& other) const {
return Res(mmod(value * other.value, T));
}
Res pow(ll degree) const {
degree = degree % (T - 1);
vector<Res<T>> deg_vals(33);
deg_vals[0] = *this;
ifor(1, 33) {
deg_vals[i] = deg_vals[i - 1] * deg_vals[i - 1];
}
Res result = 1;
for (int i = 0; degree > 0; ++i) {
if (degree % 2)
result = result * deg_vals[i];
degree /= 2;
}
return result;
}
Res reverse() const {
return pow(T - 2);
}
friend ostream& operator<<(ostream& stream, const Res& res) {
return stream << res.value;
}
};
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define yes cout << "yes\n"
#define no cout << "no\n"
void solve() {
int n;
cin >> n;
long double v; cin >> v;
vector<pair<long double, long double>> left, right;
ifor(0, n) {
long double x; cin >> x;
long double w; cin >> w;
if (x < 0) {
left.push_back(mp(x, w));
}
else {
right.push_back(mp(x, w));
}
}
auto check = [&](long double t) {
long double maxpos = -1000000000000, minpos = 1000000000000;
for (auto& [p, w] : left) {
maxpos = max(maxpos, p + w * t);
}
for (auto& [p, w] : right) {
minpos = min(minpos, p - w * t);
}
if (minpos > maxpos) {
return false;
}
return true;
};
long double l = 0, r = (right[0].first - left[0].first)/(right[0].second + left[0].second);
for (int i = 0; i < 100; ++i) {
long double m = (r + l) / 2;
if (check(m)) {
r = m;
}
else {
l = m;
}
}
cout << fixed;
cout << setprecision(9) << r * v << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3696kb
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.250000000 1.230769231 3000000000000.000000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1076ms
memory: 3680kb
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.349110037 16414958969.727281192 5202715639.835183900 321977234.156325869 45384199210.221683972 183885744.769230769 1708925225.230472358 89786664971.557942636 13924365606.287388795 412975327.555555556 965508404.512101493 4703493416.288376524 352961619.381043819 5575125771.798797157 34119...
result:
ok 10000 numbers
Test #3:
score: 0
Accepted
time: 1284ms
memory: 5188kb
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.363636364 197971181.333333333 997533531.737629592 6439673170.665741785 993821598110.661077857 22727977326.402660988 34702455207.518504031 677770533.929817499 46631726883.969133236 5446481867.129032258 11336247450.272078594 4409370840.439131625 15681606050.576286856 14986614231.546859303 10...
result:
ok 93 numbers
Test #4:
score: 0
Accepted
time: 1251ms
memory: 33016kb
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.811770916 511413015796.766475379 424240880533.634020329 518849481155.503918797 1882496988186.444000006
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 1248ms
memory: 14268kb
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.978608020 98630840901.507606961 29393530999.894327790 50801000770.955985423 39668001027.269331343 467846478226.411370844 30789914370.574311614 23151476830.905098435 51606123416.625827592 151713060001.662588924 100944679009.609286278 766785664078.358981729 39969642788.061867386 6234106593...
result:
ok 38 numbers