QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241815 | #7651. 傅里叶与交通规划 | hos_lyric# | 40 | 381ms | 96272kb | C++14 | 6.2kb | 2023-11-06 17:55:04 | 2024-07-04 02:22:57 |
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 <random>
#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; }
#define COLOR(s) ("\x1b[" s "m")
using Double = double;
constexpr Double INF = 1e+100;
int N, Q;
Int V;
vector<Int> P;
vector<Int> W;
vector<Int> X0, Y0, X1, Y1;
int indexOf(Int x) {
return (upper_bound(P.begin(), P.end(), x) - P.begin()) - 1;
}
namespace rmq {
constexpr int E = 18;
Int mn[E][1 << E], mx[E][1 << E];
void init() {
mn[0][0] = mx[0][0] = 0;
mn[0][N + 1] = mx[0][N + 1] = 0;
for (int i = 0; i < N; ++i) {
mn[0][i + 1] = mx[0][i + 1] = W[i];
}
for (int e = 0; e < E - 1; ++e) {
for (int i = 0; i + (1 << (e + 1)) <= N + 2; ++i) {
mn[e + 1][i] = min(mn[e][i], mn[e][i + (1 << e)]);
mx[e + 1][i] = max(mx[e][i], mx[e][i + (1 << e)]);
}
}
}
pair<Int, Int> get(int iL, int iR) {
if (iL > iR) swap(iL, iR);
assert(-1 <= iL); assert(iL <= iR); assert(iR <= N);
iL += 1;
iR += 2;
const int e = 31 - __builtin_clz(iR - iL);
return make_pair(
min(mn[e][iL], mn[e][iR - (1 << e)]),
max(mx[e][iL], mx[e][iR - (1 << e)])
);
}
} // rmq
namespace brute {
vector<Int> fs;
Int calc(Int x) {
const int i = indexOf(x);
if (i < 0) return 0;
if (i >= N) return fs[N];
return fs[i] + W[i] * (x - P[i]);
}
vector<Double> run() {
cerr<<"[brute::run]"<<endl;
fs.assign(N + 1, 0);
for (int i = 0; i < N; ++i) {
fs[i + 1] = fs[i] + W[i] * (P[i + 1] - P[i]);
}
vector<int> lefSmall(N), rigSmall(N);
vector<int> lefLarge(N), rigLarge(N);
{
vector<pair<Int, int>> wis(N);
for (int i = 0; i < N; ++i) wis[i] = make_pair(W[i], i);
sort(wis.begin(), wis.end());
{
set<int> is{-1, N};
for (int jL = 0, jR = 0; jL < N; jL = jR) {
for (; jR < N && wis[jL].first == wis[jR].first; ++jR) {}
for (int j = jL; j < jR; ++j) {
const int i = wis[j].second;
auto it = is.lower_bound(i);
rigSmall[i] = *it;
lefSmall[i] = *--it;
}
for (int j = jL; j < jR; ++j) {
const int i = wis[j].second;
is.insert(i);
}
}
}
reverse(wis.begin(), wis.end());
{
set<int> is{-1, N};
for (int jL = 0, jR = 0; jL < N; jL = jR) {
for (; jR < N && wis[jL].first == wis[jR].first; ++jR) {}
for (int j = jL; j < jR; ++j) {
const int i = wis[j].second;
auto it = is.lower_bound(i);
rigLarge[i] = *it;
lefLarge[i] = *--it;
}
for (int j = jL; j < jR; ++j) {
const int i = wis[j].second;
is.insert(i);
}
}
}
}
// cerr<<"W = "<<W<<endl;
// cerr<<" lefSmall = "<<lefSmall<<", rigSmall = "<<rigSmall<<endl;
// cerr<<" lefLarge = "<<lefLarge<<", rigLarge = "<<rigLarge<<endl;
vector<Double> ans(Q, INF);
for (int q = 0; q < Q; ++q) {
const Int f0 = calc(X0[q]);
const Int f1 = calc(X1[q]);
auto check = [&](Int w, Int x, Int f) -> void {
Int dx = 0, dy = 0;
dx += abs(x - X0[q]);
dx += abs(x - X1[q]);
dy += (X0[q] <= x) ? (f - f0) : (f0 - f);
dy += (X1[q] <= x) ? (f - f1) : (f1 - f);
/*
yoko: (dx/V) sec
tate: katteni (dy/V)
*/
Double cost = 0.0;
cost += (Double)dx / V;
if (V * (Y1[q] - Y0[q]) >= dy) {
cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w + V);
} else {
cost += ((Y1[q] - Y0[q]) - (Double)dy / V) / (w - V);
}
// cerr<<"check i="<<i<<" x="<<x<<" f="<<f<<": w="<<w<<", dx="<<dx<<", dy="<<dy<<", cost="<<cost<<endl;
chmin(ans[q], cost);
};
const int i0 = indexOf(X0[q]);
const int i1 = indexOf(X1[q]);
const auto inside = rmq::get(i0, i1);
check(inside.first, X0[q], f0);
check(inside.second, X0[q], f0);
/*
for (int i = min(i0, i1); i >= 0; --i) {
check((i == 0) ? 0 : W[i - 1], P[i], fs[i]);
}
for (int i = max(i0, i1) + 1; i <= N; ++i) {
check((i == N) ? 0 : W[i], P[i], fs[i]);
}
*/
check(0, P[0], fs[0]);
check(0, P[N], fs[N]);
for (int i = min(i0, i1) - 1; i >= 0; i = lefSmall[i]) check(W[i], P[i + 1], fs[i + 1]);
for (int i = min(i0, i1) - 1; i >= 0; i = lefLarge[i]) check(W[i], P[i + 1], fs[i + 1]);
for (int i = max(i0, i1) + 1; i < N; i = rigSmall[i]) check(W[i], P[i], fs[i]);;
for (int i = max(i0, i1) + 1; i < N; i = rigLarge[i]) check(W[i], P[i], fs[i]);;
}
return ans;
}
} // brute
int main() {
for (; ~scanf("%d%d%lld", &N, &Q, &V); ) {
P.resize(N + 1);
for (int i = 0; i <= N; ++i) {
scanf("%lld", &P[i]);
}
W.resize(N);
for (int i = 0; i < N; ++i) {
scanf("%lld", &W[i]);
}
X0.resize(Q);
Y0.resize(Q);
X1.resize(Q);
Y1.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%lld%lld%lld%lld", &X0[q], &Y0[q], &X1[q], &Y1[q]);
}
rmq::init();
const auto ans = brute::run();
for (int q = 0; q < Q; ++q) {
printf("%.8f\n", ans[q]);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 53ms
memory: 15140kb
input:
0 149997 245221 260130 -353413 28107 189392 258734 122083 -105519 88981 -462313 62982 -221175 258110 442570 177977 -216904 -444299 246103 134500 179401 -402939 -459279 98037 -470438 -69318 43668 -204852 443991 -303144 -468157 -19237 -321861 40988 -450597 298668 -155343 -121990 491091 -446262 2335 -...
output:
3.15402025 1.58997802 3.50244473 4.42573434 4.79615938 2.77896673 4.12052801 0.77057430 4.35155227 0.78707370 2.41183259 3.24564780 4.03301512 2.32130609 1.24432655 4.13647281 2.06239270 2.43803345 2.29035441 2.68600976 3.05624314 3.45513639 3.94013155 2.41386749 4.75957198 3.09785867 0.37262714 0.3...
result:
ok 149997 numbers
Test #2:
score: 0
Accepted
time: 2ms
memory: 9928kb
input:
0 100 180744 464809 345260 -467272 -358539 328967 -47960 301643 54141 -6592 -43596 319458 -354462 -459419 -92196 310800 -85882 335949 153982 440647 336749 -116156 101998 -66169 149181 43052 -149130 -353 -398781 416947 -291725 221463 -136712 391161 105694 -5114 87525 234469 21942 -235999 209836 6442...
output:
8.29924092 2.27026070 6.02920706 0.17407493 4.09180941 0.86533440 3.69003120 1.79652437 1.42606117 2.70171071 2.86964436 4.16984243 3.87484508 4.18178750 4.62944828 3.62348404 3.76117050 2.17181207 3.82678263 1.22877661 4.10372129 2.52296065 2.96553689 4.42727283 3.63646373 2.52484177 5.38372505 6.7...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 9928kb
input:
0 96 112916 108050 -365188 332547 492134 -36526 -104666 473952 170125 173190 -234758 166079 187562 394112 -60172 -420595 -214538 460150 10825 55480 -120065 416458 351912 -140831 -73406 308683 -217445 -459449 51277 -72378 -176912 150232 144434 162328 -50628 -400429 -319790 -371228 327358 480500 3347...
output:
10.86112686 5.09717843 5.75961777 9.16708881 4.35605229 7.74763541 5.80779518 2.95300932 2.64234475 3.16722165 4.35376740 4.60013638 8.28630132 2.48132240 9.70007793 5.11102058 1.89044954 11.16963938 11.24308335 9.67789330 11.31193985 5.80470438 6.70501080 2.60430763 2.29521946 6.76313366 3.44829785...
result:
ok 96 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 10008kb
input:
0 98 22895 91189 -107939 77752 -276636 60647 386902 -56253 293764 -430313 231497 65839 344043 304956 -391967 441156 -160698 -32346 -64780 -107106 -221509 484371 -91709 224130 432009 480623 -489838 249592 -392494 -46576 -467214 -156595 -15098 -382701 -34447 443533 154513 317948 8797 -276399 434059 7...
output:
8.11539637 20.40611487 15.35981655 30.78274732 32.67988644 34.07778991 17.18768290 29.62314916 13.73858921 33.91945840 21.46490500 45.53858921 63.71260100 37.09071850 44.31640096 31.28464730 36.31661935 30.56217515 14.79423455 34.37287617 43.04564315 9.60397467 19.62590085 41.22747325 36.55562350 28...
result:
ok 98 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 9924kb
input:
0 100 150548 10776 -338992 -479131 59003 172812 -231402 248648 269139 168600 -447255 262673 -479943 129977 266443 -494085 -99721 -439611 -328970 -239053 151827 -95253 144393 282865 221465 477090 265238 -268953 117580 107627 -320233 -224623 -394376 -382842 260411 288143 362003 -231710 -327178 195775...
output:
6.97410793 3.85650424 1.09854664 2.79404575 4.14882297 1.80206313 3.48219837 1.54344129 4.12788612 1.54292983 5.65552515 2.31542100 7.00387916 2.47851184 4.89175545 6.34711853 8.74582193 3.32192390 1.27725377 2.92590403 4.03245477 5.15509339 7.35045965 6.13361187 6.32190398 5.31443128 4.88996201 4.3...
result:
ok 100 numbers
Subtask #2:
score: 10
Accepted
Test #6:
score: 10
Accepted
time: 0ms
memory: 42848kb
input:
993 999 316326 -496532 -496093 -495620 -492330 -492168 -490309 -490221 -489706 -489674 -488540 -487445 -487205 -487063 -486731 -486636 -486525 -483675 -483348 -482170 -480225 -478996 -477851 -477476 -476245 -474426 -473611 -473054 -472532 -470524 -470223 -469519 -469003 -468790 -468648 -468210 -4680...
output:
0.99010577 1.57607674 2.57334584 2.67164505 2.52050013 2.59312045 1.12071575 3.34263720 0.35232732 3.94401275 2.03752604 1.98331717 2.35556910 1.09670729 3.20188003 0.71721534 2.19390824 1.56526473 2.40689070 1.58574632 0.91850959 2.55687581 0.83284001 0.76295398 1.37607412 2.91979169 1.08532667 3.4...
result:
ok 999 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 43092kb
input:
997 997 217603 -499799 -498333 -497404 -496957 -496655 -494826 -493913 -493091 -492990 -491277 -490056 -488767 -486657 -486543 -486528 -484217 -480512 -479591 -479562 -479559 -479159 -475469 -475297 -474181 -472973 -472661 -471212 -469422 -468661 -467326 -466468 -466262 -466067 -465341 -464845 -4643...
output:
1.10315413 2.04213627 2.80220658 2.96301554 1.25719017 0.59102322 2.00148114 1.38669390 0.49166153 2.50589746 2.63206611 1.11855330 1.72002029 3.93561193 1.87906938 2.36731687 5.85708015 0.15208288 1.18437640 5.54827737 2.12456558 3.09177448 3.97089190 1.95963096 2.62222884 3.66790539 3.31215838 1.7...
result:
ok 997 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 43128kb
input:
990 999 410563 -499636 -499493 -498362 -497772 -496607 -496251 -495502 -495291 -493565 -492200 -491876 -491569 -490203 -488666 -488637 -486272 -484197 -483586 -482754 -478432 -477269 -475235 -475067 -474547 -473480 -473411 -472262 -472236 -471888 -471339 -470160 -469159 -468072 -467881 -467211 -4661...
output:
1.45568369 0.85106182 1.59002304 1.63750780 1.47689464 0.87829694 0.52454148 0.70728837 1.00942848 1.21703711 0.55728022 0.96556329 0.76301772 1.66156757 1.47066171 1.42251255 2.14472562 0.86770401 2.48698503 0.58205739 1.12521280 0.84184861 0.99341925 0.89837199 0.79614209 1.49971601 1.10132344 0.5...
result:
ok 999 numbers
Test #9:
score: 0
Accepted
time: 4ms
memory: 42916kb
input:
999 991 278604 -499261 -498572 -498286 -495372 -493428 -492225 -490363 -487496 -487171 -485925 -484689 -484522 -483834 -482217 -481524 -481508 -479914 -478464 -477272 -476511 -475715 -475488 -475103 -473881 -472520 -471545 -468813 -467921 -467847 -467545 -465121 -464313 -462531 -462228 -461384 -4602...
output:
3.02300376 2.35961578 3.53346494 2.09374885 2.54324049 2.98178258 2.65666740 0.90686289 1.38028495 2.28961727 1.84235312 2.71083706 2.04573392 3.46622063 3.35640086 3.86226570 5.07207131 1.67539852 2.26548459 0.43374126 1.33803913 0.41368930 1.71830339 2.56779661 3.55257242 2.85706133 2.03814615 3.3...
result:
ok 991 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 43112kb
input:
998 995 86259 -499764 -499107 -497424 -497246 -496766 -496696 -495855 -495537 -494905 -494468 -490023 -488774 -487401 -486388 -484946 -483405 -483153 -482740 -481457 -480043 -479973 -477456 -477212 -477029 -476323 -473012 -472991 -472761 -472734 -472112 -471906 -471690 -471578 -469858 -469637 -46872...
output:
5.51117669 5.94012013 12.87262087 4.94578325 2.31966038 10.89187986 12.02043319 7.68111978 3.24887869 10.40333746 12.58159340 9.71068730 2.15219750 6.12110270 10.75168657 7.34640668 8.21922217 8.60182083 8.64925664 12.41368190 4.77069304 8.28747830 2.55960575 9.92515972 9.05260941 13.00865596 7.4206...
result:
ok 995 numbers
Subtask #3:
score: 10
Accepted
Test #11:
score: 10
Accepted
time: 229ms
memory: 95596kb
input:
149928 149904 81074 -499992 -499987 -499981 -499968 -499965 -499961 -499949 -499941 -499940 -499933 -499925 -499923 -499911 -499899 -499893 -499892 -499877 -499868 -499865 -499858 -499852 -499849 -499845 -499838 -499837 -499836 -499826 -499822 -499819 -499815 -499803 -499801 -499797 -499785 -499783 ...
output:
16.85484255 14.99717971 15.81377823 16.64635760 13.26417734 14.49516610 13.76456979 14.23752335 12.53687517 15.46044490 13.33098133 14.53125681 13.98715794 16.95971100 14.12009115 12.95943964 15.13091021 14.89997779 12.70265067 14.60811429 14.16696392 14.73608946 16.36595002 12.87520397 17.25445860 ...
result:
ok 149904 numbers
Test #12:
score: 0
Accepted
time: 27ms
memory: 72260kb
input:
49934 90 22588 -499984 -499964 -499955 -499950 -499937 -499923 -499867 -499863 -499860 -499854 -499851 -499795 -499784 -499737 -499731 -499729 -499709 -499703 -499701 -499678 -499676 -499673 -499655 -499590 -499587 -499559 -499536 -499488 -499465 -499453 -499447 -499371 -499351 -499338 -499335 -4993...
output:
51.65172809 45.77828498 58.73637855 48.50674098 54.04567150 48.75563971 64.87588321 45.71893800 44.44781459 46.88230269 45.80852294 50.52098917 60.25123223 61.66928243 47.14567845 45.07119035 47.35739949 50.28456999 52.47920363 44.55603145 44.46638681 56.41170064 55.76019756 61.66244657 53.09910932 ...
result:
ok 90 numbers
Test #13:
score: 0
Accepted
time: 6ms
memory: 55796kb
input:
4964 92 138367 -499797 -499471 -499299 -499268 -498616 -498541 -498312 -497850 -497119 -496699 -496505 -496336 -496195 -495977 -495739 -495693 -495376 -495255 -495240 -495084 -495061 -494981 -494958 -494841 -494830 -494713 -494615 -494334 -493926 -493804 -493711 -493618 -493583 -493537 -493414 -4930...
output:
8.51911185 7.69964487 8.83104228 7.41149921 10.00588952 8.66494355 8.49453501 8.84660241 7.54651532 8.64001571 8.63602037 7.87768652 8.89298285 7.53201640 8.30546576 7.34587787 8.35959869 7.44396159 8.57703571 8.86774081 7.59168521 7.83628922 9.04076158 8.88027315 8.37110075 8.33400362 9.79369220 8....
result:
ok 92 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 38664kb
input:
473 91 280891 -499695 -491193 -490954 -488064 -487152 -486813 -486653 -483884 -483780 -483560 -482582 -478635 -477514 -469765 -468404 -463396 -459567 -459150 -458362 -457468 -456519 -455992 -453760 -447451 -445214 -443060 -439883 -438546 -431873 -422100 -416682 -415799 -408108 -403186 -402593 -40244...
output:
4.99715489 4.10254530 4.67681200 4.69592650 3.93638151 3.56008568 3.56435944 4.79774508 4.30378529 4.81691807 3.71844565 4.30936295 3.72882050 4.60790391 3.98717030 3.95525638 3.61683372 3.84615420 4.48827995 4.90758055 4.40088936 3.95280530 5.19179450 4.47521039 5.14411633 3.58170075 4.18386990 4.5...
result:
ok 91 numbers
Test #15:
score: 0
Accepted
time: 122ms
memory: 86584kb
input:
99944 149372 113369 -499995 -499983 -499979 -499978 -499964 -499950 -499946 -499929 -499923 -499921 -499914 -499893 -499880 -499863 -499831 -499814 -499805 -499796 -499788 -499787 -499781 -499779 -499748 -499747 -499745 -499734 -499700 -499698 -499695 -499688 -499665 -499660 -499640 -499630 -499624 ...
output:
10.66995160 10.22523371 9.40459231 13.11014646 9.45820407 10.67284482 11.12234799 12.13606873 8.94030448 8.86788140 11.12247826 10.21857010 8.86418539 11.12636392 10.23832479 9.26073740 9.33277240 11.39729291 9.52413067 10.60661390 10.61586691 9.63188106 9.46534450 9.02182624 9.19026368 10.92778336 ...
result:
ok 149372 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 42872kb
input:
854 92 154270 -498878 -498558 -498030 -496154 -495734 -495439 -494928 -492469 -489873 -489750 -489153 -488956 -486460 -485436 -485019 -484168 -484159 -483513 -482927 -482269 -480851 -480501 -477526 -476301 -475337 -474926 -474617 -473968 -471575 -471389 -471126 -470407 -469246 -468844 -468789 -46854...
output:
7.00593540 6.62119124 7.10736216 7.12663209 6.56044703 6.69440919 6.77164931 9.30981800 8.03545417 7.37545167 6.74030618 7.16472267 7.17813797 6.70805669 7.89829824 6.49230272 6.49141834 8.44668419 6.60850166 7.02005249 7.32439933 7.15388170 7.08649212 9.42871893 7.02973256 8.00548413 7.62910608 6.4...
result:
ok 92 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 42928kb
input:
811 97 204269 -499023 -498121 -496051 -494631 -493384 -492924 -492159 -491576 -489519 -488007 -487026 -485511 -484439 -483918 -480089 -479139 -478859 -475982 -475457 -472489 -472374 -471297 -468837 -468199 -466579 -464763 -463487 -462936 -461462 -459463 -457411 -454221 -453778 -453325 -448427 -44791...
output:
6.36939258 6.32327795 5.32598885 6.97236746 6.49094947 6.88560163 5.01994406 5.14398458 4.93968032 4.89196379 5.52001753 6.89457673 5.25294522 5.22100834 5.00775807 6.29387685 7.15555256 6.90054462 6.44042716 5.61074397 5.29649715 4.92208731 5.11718370 5.24878249 4.89919411 6.52862803 5.26184076 5.8...
result:
ok 97 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 26336kb
input:
44 92 23756 -455424 -411003 -394907 -345645 -344017 -301113 -285315 -272511 -248317 -205733 -183557 -179295 -160321 -90555 -61719 -60568 -48097 -47091 -38706 -35645 -31598 -17875 -6000 27003 53825 80267 80971 87486 110173 117577 117796 144115 145782 190489 221315 284071 317664 361721 369142 388959 3...
output:
56.89069567 52.79929958 43.13868954 41.26747494 47.43074158 43.16260996 39.86469807 45.86146044 44.71918588 47.91251703 46.51411318 52.61481291 39.83875362 58.17682227 42.70630428 47.82534374 42.53282970 44.35679055 50.74612368 48.03853083 54.34567277 45.92895969 54.76564193 41.52419299 46.39687256 ...
result:
ok 92 numbers
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Test #19:
score: 10
Accepted
time: 236ms
memory: 96272kb
input:
149911 149947 116886 -499997 -499992 -499991 -499971 -499963 -499944 -499929 -499919 -499901 -499896 -499889 -499885 -499874 -499872 -499869 -499865 -499857 -499851 -499846 -499839 -499830 -499829 -499828 -499820 -499817 -499810 -499809 -499789 -499777 -499773 -499771 -499770 -499769 -499764 -499763...
output:
5.03500346 6.80069196 7.42041176 4.77755811 5.91877121 5.48878282 7.20968551 5.54992327 8.26868187 5.11020441 4.92583633 7.66136092 6.11245027 5.51023350 4.98506057 7.31379886 5.97539693 6.03123554 7.36567464 5.62849002 5.98901329 6.44867930 7.73731343 5.45358583 5.77809454 5.42859546 6.00820366 4.8...
result:
ok 149947 numbers
Test #20:
score: 0
Accepted
time: 42ms
memory: 72464kb
input:
49998 976 4301 -499995 -499977 -499966 -499952 -499950 -499933 -499880 -499857 -499856 -499830 -499821 -499809 -499794 -499772 -499764 -499706 -499703 -499692 -499667 -499661 -499652 -499648 -499645 -499631 -499559 -499557 -499553 -499544 -499520 -499482 -499462 -499371 -499334 -499325 -499313 -4993...
output:
114.93071125 57.40564436 31.72331332 33.11000202 69.96094959 63.19789747 51.73331681 32.06285036 115.65947302 62.39296552 93.32672101 37.98001714 68.41415270 44.28881844 90.09518723 42.25324118 47.17661098 79.23302601 58.61688084 49.15395040 52.28056359 40.68062401 52.29897925 102.41320514 119.37032...
result:
ok 976 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 42908kb
input:
975 953 93061 -492823 -492732 -492028 -491965 -491471 -491081 -490667 -490639 -487837 -487619 -486792 -486356 -484286 -484110 -481761 -481264 -480617 -480485 -478327 -477885 -476349 -476237 -476008 -474874 -474014 -471434 -470499 -468490 -467607 -467230 -467222 -467149 -464670 -463610 -462464 -46069...
output:
3.49617382 3.86421867 2.99902025 3.17260391 3.69646491 2.67678403 4.81260909 3.91196273 4.59904698 4.35061293 4.30572586 5.35192284 6.82154172 2.86055310 2.78892756 2.55896008 4.54221985 3.84520083 2.49452970 6.01004369 2.48954386 4.94696353 3.69292332 4.87916126 4.49365104 7.14540028 5.31145251 7.2...
result:
ok 953 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 30524kb
input:
94 904 44506 -484085 -455725 -454829 -451090 -445346 -432295 -426196 -425404 -405212 -393305 -392640 -350172 -329071 -325454 -292817 -288714 -286102 -276925 -260864 -247808 -244808 -219022 -210685 -203440 -199935 -199520 -199078 -171835 -129706 -118160 -115764 -99952 -87065 -72779 -71852 -63658 -617...
output:
13.91746864 6.98179073 16.06942269 16.08955205 8.59256962 7.05600659 7.53928786 7.75463753 8.37204078 11.45068534 12.69791435 9.32246817 9.03623390 12.10048169 9.36762991 14.82475776 10.49914251 7.85546825 6.13752797 8.85698818 7.24938119 10.82177848 12.96893163 8.96971412 11.44495423 15.95460700 8....
result:
ok 904 numbers
Test #23:
score: -10
Time Limit Exceeded
input:
99912 149987 148904 -499993 -499992 -499988 -499982 -499980 -499978 -499963 -499959 -499948 -499923 -499922 -499910 -499909 -499901 -499898 -499886 -499874 -499862 -499861 -499853 -499841 -499838 -499820 -499816 -499815 -499813 -499803 -499794 -499787 -499775 -499733 -499732 -499724 -499723 -499721 ...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #27:
score: 0
Time Limit Exceeded
input:
149957 149927 72015 -499992 -499989 -499986 -499981 -499980 -499970 -499957 -499950 -499947 -499937 -499929 -499928 -499925 -499915 -499913 -499905 -499885 -499881 -499868 -499859 -499856 -499852 -499848 -499839 -499835 -499828 -499821 -499815 -499814 -499809 -499808 -499799 -499797 -499792 -499783 ...
output:
result:
Subtask #6:
score: 0
Time Limit Exceeded
Test #34:
score: 15
Accepted
time: 359ms
memory: 95992kb
input:
149278 149093 342851 -499997 -499996 -499993 -499975 -499974 -499969 -499955 -499954 -499942 -499939 -499935 -499934 -499926 -499905 -499901 -499895 -499893 -499883 -499882 -499872 -499865 -499862 -499859 -499815 -499807 -499805 -499799 -499779 -499765 -499755 -499741 -499736 -499729 -499701 -499688...
output:
1.23446280 1.08260762 0.67585857 0.59273972 0.51481140 0.09565943 0.15518115 0.06583307 0.46282966 0.05887430 0.11873674 0.69494125 0.02925277 0.26799179 0.01014910 0.67951105 1.09445186 0.45012580 0.32870133 0.71116124 0.01043230 0.07701389 0.38537240 0.58054998 0.79641831 0.42444881 1.03460451 1.1...
result:
ok 149093 numbers
Test #35:
score: 0
Accepted
time: 46ms
memory: 72324kb
input:
49950 9663 218965 -499987 -499977 -499952 -499947 -499870 -499828 -499824 -499798 -499787 -499774 -499763 -499756 -499741 -499718 -499712 -499707 -499675 -499660 -499631 -499579 -499555 -499553 -499537 -499532 -499531 -499502 -499493 -499464 -499399 -499389 -499373 -499322 -499313 -499270 -499182 -4...
output:
0.75482748 1.10303987 1.37927977 0.14098450 1.98119733 0.03559078 0.17484048 0.11065824 1.80276529 1.59381671 1.00966073 0.74568952 0.57872315 1.47537978 1.45743565 0.28376634 0.95626209 1.45280941 0.50903692 0.28048300 0.25704121 0.23162779 1.84243489 0.71614840 0.71423671 1.43910238 0.17710547 1.8...
result:
ok 9663 numbers
Test #36:
score: 0
Accepted
time: 3ms
memory: 55548kb
input:
4995 932 493038 -499937 -499747 -499287 -499117 -499070 -498902 -498704 -498628 -498537 -497816 -497759 -497331 -496999 -496719 -496109 -495954 -495482 -495041 -494685 -494298 -494204 -493930 -493885 -493456 -493114 -493014 -492957 -492503 -492311 -492265 -491100 -491025 -490863 -490701 -490526 -490...
output:
0.53334985 0.25264396 0.78739186 0.01986276 0.07752463 0.07989210 0.17769833 0.47086217 0.70777652 0.79304351 0.41535042 0.37691245 0.13398433 0.73807630 0.35517617 0.23863921 0.35858065 0.65708886 0.27712402 0.04590901 0.12421497 0.40220083 0.17647402 0.49524977 0.25435949 0.38640143 0.87857545 0.4...
result:
ok 932 numbers
Test #37:
score: 0
Accepted
time: 0ms
memory: 38952kb
input:
367 910 93569 -494593 -492783 -491608 -491398 -486772 -485715 -485133 -482589 -475662 -474200 -469800 -465963 -464254 -463888 -456575 -454713 -454155 -450740 -441318 -437684 -435619 -435110 -429607 -423889 -421753 -418100 -411326 -409590 -407824 -406727 -404200 -402472 -402348 -401394 -398549 -39820...
output:
1.68848267 1.09031458 0.69093451 5.17195066 2.94588190 2.74507622 1.28291631 1.90122252 4.03623979 4.95994791 1.94069467 0.37519475 4.78841567 4.35708547 4.13314439 0.21093435 4.28748488 1.16533476 0.63113539 3.90222085 2.30144897 1.55889925 2.34269227 3.94854109 3.77019500 0.82579465 1.65361220 2.0...
result:
ok 910 numbers
Test #38:
score: 0
Accepted
time: 0ms
memory: 43052kb
input:
831 932 430975 -499988 -498573 -498078 -495703 -494248 -493478 -493238 -492018 -490139 -488536 -488434 -487719 -487380 -483132 -478519 -477733 -476732 -476067 -476045 -476041 -475764 -472850 -472352 -472057 -470523 -470088 -468459 -466265 -465601 -464365 -461999 -461043 -460607 -459586 -457526 -4555...
output:
0.78708433 0.21709640 0.03859383 0.56947805 0.15072472 0.29366493 0.26779319 0.04997299 0.46627858 0.23441290 0.18951119 0.51137746 0.04405861 0.17685706 0.46002508 0.26166328 0.50502088 0.75077089 0.27006315 0.05427941 0.73331489 0.74628879 0.39747949 0.85831755 0.73319910 0.23113509 0.13015485 0.6...
result:
ok 932 numbers
Test #39:
score: -15
Time Limit Exceeded
input:
149978 149588 305623 -500000 -499995 -499988 -499983 -499982 -499971 -499968 -499966 -499960 -499954 -499953 -499952 -499950 -499949 -499929 -499920 -499908 -499897 -499888 -499885 -499879 -499877 -499875 -499874 -499872 -499868 -499864 -499862 -499851 -499846 -499843 -499841 -499840 -499839 -499837...
output:
result:
Subtask #7:
score: 15
Accepted
Test #43:
score: 15
Accepted
time: 381ms
memory: 95220kb
input:
149990 149944 141363 -499995 -499994 -499993 -499990 -499956 -499950 -499947 -499924 -499921 -499916 -499914 -499888 -499876 -499870 -499869 -499863 -499855 -499848 -499846 -499837 -499836 -499833 -499832 -499815 -499813 -499799 -499787 -499775 -499770 -499769 -499767 -499766 -499762 -499757 -499753...
output:
2.85905793 1.31671388 3.12882822 6.23474730 5.07393036 3.69524523 3.29137143 5.50028330 1.28931668 2.42087222 0.73993127 0.91882973 3.61397963 2.30513854 3.73927801 0.59207535 0.71543114 3.68421070 2.11249528 0.58018545 2.96508347 6.57030367 5.38212914 3.22122912 1.86715448 3.97327458 4.86391909 1.6...
result:
ok 149944 numbers
Test #44:
score: 0
Accepted
time: 363ms
memory: 96216kb
input:
149927 149976 2798 -499981 -499980 -499974 -499971 -499969 -499967 -499954 -499953 -499952 -499948 -499938 -499928 -499918 -499902 -499898 -499886 -499885 -499883 -499878 -499871 -499864 -499855 -499834 -499828 -499827 -499816 -499809 -499803 -499802 -499799 -499793 -499779 -499773 -499772 -499770 -...
output:
129.43248145 199.05771919 256.64906038 143.67583791 130.50764864 150.64670117 47.24497350 341.27670856 141.63823093 49.89180222 59.97951939 226.39215807 280.72088534 99.30549997 88.43650437 181.40947568 215.73452990 146.70012003 268.90219862 99.51309253 53.22662204 396.70970922 145.23109217 28.95296...
result:
ok 149976 numbers
Test #45:
score: 0
Accepted
time: 4ms
memory: 42788kb
input:
633 990 375971 -499674 -499550 -493916 -492655 -491141 -489644 -489377 -489054 -487790 -482760 -482579 -478150 -477350 -477345 -476950 -473151 -472647 -472507 -470233 -469218 -468453 -463068 -461958 -460395 -459448 -459372 -459056 -458108 -457518 -453548 -451892 -451064 -449878 -442024 -440496 -4396...
output:
1.08125890 1.00901343 1.27362447 0.04727399 0.33492772 0.41424515 1.04843391 1.09811899 1.02390269 1.06327016 2.20638670 1.95163137 2.02071186 0.34178366 1.23057616 1.17575362 1.44583550 1.21238584 1.39991219 2.53769836 1.16202710 0.90438114 3.36690076 1.93801432 2.61811347 1.50422309 1.15043044 1.0...
result:
ok 990 numbers
Test #46:
score: 0
Accepted
time: 2ms
memory: 43100kb
input:
825 995 236205 -499213 -495358 -495254 -493281 -492771 -492500 -486576 -486304 -485361 -484884 -482973 -476757 -476452 -476447 -476435 -474868 -472626 -469274 -466803 -466605 -464583 -464518 -464263 -462979 -462145 -461978 -461385 -459652 -455894 -452903 -451440 -450394 -450046 -449912 -449264 -4482...
output:
3.93668159 3.06121884 1.51456475 2.21019166 2.48529278 1.05105185 0.81644468 3.18487734 0.28197195 4.79436230 2.94016112 3.90970952 1.39917141 3.90374358 3.67697751 1.39472172 2.13065869 1.35842284 4.86304620 2.00936766 1.73338669 4.16929773 4.30663003 2.32030575 3.14169780 4.30124107 4.09467442 2.0...
result:
ok 995 numbers
Test #47:
score: 0
Accepted
time: 0ms
memory: 38908kb
input:
336 994 323417 -497309 -497035 -496446 -487637 -487318 -486982 -481391 -475964 -472481 -470249 -467508 -461235 -460923 -453811 -453415 -453094 -452867 -446051 -445912 -438676 -434322 -424520 -414188 -412705 -411025 -410378 -408410 -400585 -394921 -394840 -385111 -384853 -382761 -380545 -379531 -3785...
output:
2.26507065 1.28574252 1.58407242 1.95837532 0.87623844 2.76732988 2.38406758 0.59294729 2.32050104 0.76651295 1.68038275 1.39341457 1.48485532 1.23970017 0.92757086 0.34552716 1.25579528 3.21426597 0.37486433 0.37323106 1.18183633 0.53298827 1.29737861 2.91976543 1.13607266 2.36060073 0.74340389 1.6...
result:
ok 994 numbers
Subtask #8:
score: 0
Time Limit Exceeded
Dependency #2:
100%
Accepted
Test #48:
score: 10
Accepted
time: 109ms
memory: 73644kb
input:
49982 49912 98988 -499997 -499929 -499912 -499874 -499844 -499825 -499814 -499742 -499709 -499646 -499643 -499626 -499602 -499579 -499554 -499512 -499509 -499507 -499483 -499479 -499381 -499365 -499223 -499204 -499192 -499179 -499147 -499144 -499120 -499046 -499020 -498997 -498994 -498955 -498954 -4...
output:
7.69917377 1.91858599 4.28787383 0.89898874 10.49792470 2.63230978 4.23177722 3.71182650 0.67897894 5.55553695 4.48577694 2.01655423 4.71993301 10.96916447 7.45411816 7.05923964 0.71036674 5.90735335 7.31839422 7.11330958 4.92787063 2.74194504 1.68808867 2.61038333 2.08359038 4.00841840 4.32135865 6...
result:
ok 49912 numbers
Test #49:
score: 0
Accepted
time: 7ms
memory: 55964kb
input:
4940 4981 341461 -499494 -499394 -499304 -499154 -499096 -499077 -499051 -499008 -498915 -498781 -498684 -498511 -498027 -497794 -497633 -497334 -497221 -497187 -497149 -496719 -496574 -496488 -496388 -496372 -496323 -496303 -496079 -495918 -495375 -495146 -495067 -494634 -493879 -493792 -493483 -49...
output:
1.77184364 0.36058898 2.44614347 1.55024200 0.32806439 1.32062188 0.96939835 1.73770107 1.70576631 0.60990705 1.39448387 1.61420709 0.30403138 2.98412306 1.81274257 1.38902786 1.71289464 1.68220309 1.79867055 1.26380193 1.75869105 1.21224067 0.45327626 0.73623741 2.25829144 3.62098244 1.88710432 2.4...
result:
ok 4981 numbers
Test #50:
score: 0
Accepted
time: 0ms
memory: 38812kb
input:
496 500 346404 -497896 -497005 -495935 -495154 -491603 -490440 -488905 -483779 -479887 -471916 -471799 -470461 -470001 -469509 -467992 -467787 -467648 -467143 -466216 -462395 -461599 -461191 -457726 -455930 -453547 -451800 -448684 -448507 -446794 -446523 -446347 -443912 -440802 -440688 -439740 -4368...
output:
1.74193291 0.83762729 0.66523321 0.75708754 1.94385136 2.93198241 2.22980337 0.55117205 1.58487654 1.71298797 1.04305600 0.97107194 1.26129066 1.18387228 2.26714297 0.73377808 1.96102499 1.59135286 0.16297014 0.53913395 1.05343833 0.35571402 1.00708595 3.25590571 1.67043308 1.97542564 1.26625765 0.9...
result:
ok 500 numbers
Test #51:
score: -10
Time Limit Exceeded
input:
49369 49955 356633 -499992 -499985 -499977 -499955 -499952 -499941 -499907 -499888 -499887 -499856 -499841 -499831 -499799 -499770 -499753 -499694 -499680 -499678 -499667 -499662 -499657 -499651 -499635 -499584 -499569 -499557 -499537 -499468 -499424 -499374 -499353 -499349 -499345 -499318 -499312 -...
output:
result:
Subtask #9:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #4:
0%