QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338375 | #5570. Epidemic Escape | ucup-team1198# | TL | 3980ms | 32732kb | C++20 | 8.2kb | 2024-02-25 21:05:20 | 2024-02-25 21:05:22 |
Judging History
answer
#pragma GCC optimize("fast-math,Ofast,unroll-loops")
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define int int64_t
using ld = __float128;
ld abs(ld x) {
if (x > 0) return x;
return -x;
}
struct IVector {
int x;
int y;
IVector(int x = 0, int y = 0): x(x), y(y) {}
IVector(const IVector& a, const IVector& b): x(b.x - a.x), y(b.y - a.y) {}
};
IVector operator-(const IVector& a) {
return {-a.x, -a.y};
}
int operator%(const IVector& a, const IVector& b) {
return a.x * b.y - a.y * b.x;
}
bool hp(const IVector& v) {
if (v.y == 0) return v.x > 0;
return v.y > 0;
}
bool operator<(const IVector& a, const IVector& b) {
if (hp(a) != hp(b)) return hp(a);
return a % b > 0;
}
bool operator==(const IVector& a, const IVector& b) {
return a.x == b.x && a.y == b.y;
}
istream& operator>>(istream& in, IVector& v) {
in >> v.x >> v.y;
return in;
}
const int MAXN = 1e5 + 100;
bool is_bad[MAXN];
struct Vector {
ld x;
ld y;
Vector(ld x = 0, ld y = 0): x(x), y(y) {}
Vector(const Vector& a, const Vector& b): x(b.x - a.x), y(b.y - a.y) {}
Vector(const IVector& a): x(a.x), y(a.y) {}
Vector(const IVector& a, bool inv) {
ld ln = a.x * a.x + a.y * a.y;
x = a.x; y = a.y;
x /= ln;
y /= ln;
}
ld sqlen() const { return x * x + y * y; }
};
Vector operator-(const Vector& a, const Vector& b) {
return Vector(b, a);
}
Vector operator+(const Vector& a, const Vector& b) {
return {a.x + b.x, a.y + b.y};
}
ld operator%(const Vector& a, const Vector& b) {
return a.x * b.y - a.y * b.x;
}
ld operator*(const Vector& a, const Vector& b) {
return a.x * b.x + a.y * b.y;
}
const ld EPS = 1e-32;
const int MAXK = 6;
vector<Vector> convex(vector<Vector>& p) {
if (p.empty()) return p;
int n = p.size();
Vector minp = p[0];
for (int i = 1; i < n; ++i) {
if (p[i].x < minp.x) {
minp = p[i];
} else if (p[i].x == minp.x && p[i].y < minp.y) {
minp = p[i];
}
}
sort(p.begin(), p.end(), [&](const Vector& u, const Vector& v) {
if (abs((u - minp) % (v - minp)) < EPS) {
return (u - minp).sqlen() < (v - minp).sqlen();
}
return (u - minp) % (v - minp) < 0;
});
p.push_back(p[0]);
/**for (auto elem : p) {
cout << (double)elem.x << " " << (double)elem.y << " : ";
}
cout << endl;*/
vector<Vector> st;
int sz = 0;
vector<Vector> p1;
for (auto v : p) {
while (sz >= 2 && (st[sz - 1] - st[sz - 2]) % (v - st[sz - 1]) >= -EPS) {
p1.push_back(st.back());
st.pop_back();
--sz;
}
st.push_back(v);
++sz;
}
st.pop_back();
p = p1;
return st;
}
int norm(int x, int n) {
while (x >= n) x -= n;
return x;
}
int reduce(int x, int n) {
while (x < 0) x += n;
return x;
}
vector<Vector> get_bst(const Vector& dir, const vector<Vector>& p, int cnt) {
if (p.empty()) return p;
int n = p.size();
int k = 0;
while ((1 << k) < n) ++k;
int i = 0;
while (k >= 0) {
int i1 = norm((i + (1 << k)), n);
int i2 = reduce((i - (1 << k)), n);
if (dir * p[i1] > dir * p[i]) i = i1;
if (dir * p[i2] > dir * p[i]) i = i2;
--k;
}
vector<Vector> ans = {p[i]};
int sz = min(cnt - 1, n - 1);
int t1 = norm((i + 1) , n);
int t2 = reduce((i - 1) , n);
for (int _ = 0; _ < sz; ++_) {
if (dir * p[t1] > dir * p[t2]) {
ans.push_back(p[t1]);
t1 = norm((t1 + 1), n);
} else {
ans.push_back(p[t2]);
t2 = reduce((t2 - 1) , n);
}
}
return ans;
}
mt19937 rnd;
const int MAX = 100000000;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(10);
int n;
cin >> n;
vector<IVector> p(n);
int cnt0 = 0;
for (int i = 0; i < n; ++i) {
cin >> p[i];
/**p[i].x = rnd() % (2 * MAX) - MAX;
p[i].y = rnd() % (2 * MAX) - MAX;*/
}
vector<IVector> p1;
for (int i = 0; i < n; ++i) {
if (p[i] == IVector()) {
++cnt0;
} else {
p1.push_back(p[i]);
}
}
p = p1;
n = p.size();
int q;
cin >> q;
vector<pair<IVector, int>> qu(q);
for (int i = 0; i < q; ++i) {
cin >> qu[i].first >> qu[i].second;
/**qu[i].first.x = rnd() % (2 * MAX) - MAX;
qu[i].first.y = rnd() % (2 * MAX) - MAX;
qu[i].second = 5;*/
qu[i].second -= cnt0;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (hp(p[i])) ++cnt;
}
vector<pair<IVector, int>> ev;
for (int i = 0; i < n; ++i) {
ev.push_back({p[i], -1});
ev.push_back({-p[i], q});
}
for (int i = 0; i < q; ++i) {
if (qu[i].first == IVector()) {
is_bad[i] = true;
continue;
}
ev.push_back({{qu[i].first.y, -qu[i].first.x}, i});
}
sort(ev.begin(), ev.end());
for (auto elem : ev) {
if (elem.second == -1) {
--cnt;
} else if (elem.second == q) {
++cnt;
} else {
if (cnt < qu[elem.second].second) {
is_bad[elem.second] = true;
}
}
}
vector<Vector> pv;
for (int i = 0; i < n; ++i) {
pv.push_back(Vector(p[i], true));
/// cerr << i << ": " << (double)pv[i].x << " " << (double)pv[i].y << endl;
}
vector<vector<Vector>> hulls;
for (int i = 0; i < MAXK; ++i) {
hulls.push_back(convex(pv));
/**for (Vector v : hulls.back()) {
cout << (double)v.x << " " << (double)v.y << "; ";
}
cout << endl;*/
}
for (int i = 0; i < q; ++i) {
if (is_bad[i]) {
cout << "-1\n";
continue;
}
if (qu[i].second <= 0) {
cout << "0\n";
continue;
}
int k = qu[i].second;
Vector dir = qu[i].first;
vector<Vector> bst;
for (int i = 0; i <= k; ++i) {
auto res = get_bst(dir, hulls[i], max(k - i, (int)1));
/**vector<Vector> bst1;
int f1 = 0, f2 = 0;
for (int i = 0; i <= k && i < (int)bst.size() + res.size(); ++i) {
if (f2 >= res.size()) {
bst1.push_back(bst[f1++]);
} else if (f1 >= bst.size()) {
bst1.push_back(res[f2++]);
} else if (bst[f1] * dir > res[f2] * dir) {
bst1.push_back(bst[f1++]);
} else {
bst1.push_back(res[f2++]);
}
}
bst = move(bst1);*/
for (auto elem : res) {
bst.push_back(elem);
for (int i = (int)bst.size() - 1; i > 0; --i) {
if (dir * bst[i] > dir * bst[i - 1]) {
swap(bst[i], bst[i - 1]);
} else {
break;
}
}
if ((int)bst.size() > k) bst.pop_back();
}
}
long double ans = dir * bst[k - 1];
/// cout << (double)bst[k - 1].x << " " << (double)bst[k - 1].y << endl;
ans /= sqrtl(dir.x * dir.x + dir.y * dir.y);
ans = 0.5 / ans;
cout << ans << "\n";
if (ans < -1) {
cout << n << "\n";
for (int i = 0; i < n; ++i) {
cout << p[i].x << " " << p[i].y << "\n";
}
cout << qu[i].first.x << " " << qu[i].first.y << " " << qu[i].second << endl;
return 0;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
input:
5 5 -3 5 4 -6 2 -5 0 4 1 2 -3 -10 1 6 -9 1
output:
8.7002554241 3.2260195623
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
8 4 -1 4 -8 0 9 4 -7 -5 -2 5 -5 7 5 -9 2 10 4 -8 1 7 -7 5 -10 8 2 -9 9 2 4 -7 5 -1 -10 2 6 -3 2 2 -9 3 -10 -10 1 5 9 1
output:
3.1677629681 26.1629509039 5.4614883202 6.3639610307 -1 5.2894082216 3.7267799625 4.6097722286 2.9294423792 4.7617289402
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
5 -4 -7 5 0 2 4 -7 -7 4 4 20 0 -5 2 -4 -7 2 -7 7 3 4 -4 3 -7 4 3 4 -4 1 2 4 1 6 -7 2 4 -4 2 4 4 3 5 4 1 -1 9 2 8 9 3 4 -4 2 6 3 3 -10 -3 2 -7 7 1 9 -4 1 -4 -7 3 -2 0 2
output:
7.0000000000 5.1305276580 -1 -1 -1 3.5355339059 2.2360679775 11.9854077945 15.3206469257 3.5355339059 2.4627400913 4.5276925691 3.7629983059 15.3206469257 2.9814239700 5.6217035048 7.0710678119 2.7357938338 -1 8.1250000000
result:
ok 20 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
100 63 -48 20 -62 -81 -31 -17 -93 2 -74 72 25 -71 37 -71 17 56 67 -47 65 -89 14 62 30 -71 -33 14 -53 -57 -52 30 80 -14 -69 -45 -19 -54 -71 58 -20 -57 12 5 -56 -76 -2 26 61 24 60 10 -97 -63 38 17 81 -43 -38 44 35 -86 37 62 72 77 11 41 29 14 81 77 55 -54 -33 -43 -51 76 14 55 47 43 24 69 -13 16 75 11 9...
output:
26.7586788688 29.5714059979 24.6221445045 27.7717456547 26.6783667129 24.4237024605 28.8933481964 29.7761695578 31.9403629705 27.2149016024 31.7280950457 27.0711605517 25.2991100306 26.8710651521 28.9958394534 28.3563142462 29.9872588920 25.6496237196 25.1496681332 28.3011569706 28.6117519545 26.690...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 174ms
memory: 5636kb
input:
10000 -3 3 -6 2 -4 1 -2 -5 5 -6 -7 -2 0 7 1 -4 8 0 -4 4 -6 -2 5 0 2 9 -4 -8 0 -8 7 4 -7 2 3 3 4 1 -1 7 -4 -2 6 0 3 -5 -7 2 0 -9 7 0 7 3 -6 0 1 7 6 2 2 -9 1 8 3 -3 2 -9 4 2 4 -5 6 0 -3 6 7 3 0 8 0 -4 7 0 -5 8 5 -5 -5 -1 0 9 -4 -3 -9 -1 7 -2 -7 -2 4 0 -6 6 -3 4 6 7 2 5 -8 -5 0 5 4 0 0 -4 0 -6 -5 3 -5 ...
output:
2.1549170046 2.1672659357 2.0676430855 2.1118419787 2.1118419787 2.1118419787 2.1249872786 2.1213203436 2.0275875101 2.0928822829 2.1415372144 2.0615528128 2.1549170046 2.0000000000 2.1213203436 2.1672659357 2.0676430855 2.0203050891 2.0676430855 2.1415372144 2.1213203436 2.0000000000 2.1213203436 2...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 196ms
memory: 5812kb
input:
10000 -90174 318421 -37261 138897 -260388 -302590 -906833 35071 317743 -283220 390311 -85301 880987 325969 -315218 -116767 103089 -8223 -134988 -973121 -444593 229407 -552060 549321 265624 -337609 -264546 322379 28687 110143 467764 303005 -335748 32188 213125 274156 240105 751 -81255 -129323 148563 ...
output:
218.3023759373 481.6627119891 792.1850756018 579.9542618493 807.7094462678 242.5921754846 882.2675147667 530.7807802597 664.1821759610 796.3607397675 662.7071678987 639.0726192787 125.8211827153 745.7291752667 732.4967218100 676.5327801482 808.9964118683 427.9627407901 1298.3736892031 616.3789303001...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 2003ms
memory: 30492kb
input:
100000 -14593321 17388753 13488647 1223793 33907737 -8731155 -14502324 73522129 -13933178 -13752140 9462275 13349398 14636622 31405249 5160247 -69775840 -49415260 -40092130 -9926862 -25806124 14982829 -8025116 -5492901 4568113 48872077 86636033 19374632 32538501 -16657133 -11624530 -15398598 -966935...
output:
1331.4977763324 1193.9602287451 1171.2427261871 1856.2890362990 2681.8829458540 1170.8707408363 1128.3614715722 1855.8783379892 3518.3241479702 1541.7860082154 1515.0151223165 1124.4065660466 2146.7167113138 1179.4306789471 1164.1588782715 1251.5110829082 2737.3506509053 1117.3515869945 2213.1263918...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 1549ms
memory: 28092kb
input:
100000 -60674143 79489917 99210432 12541486 -99948887 -3196593 57015830 -82153478 10407645 99456921 -90320128 42921703 93983821 34161956 96773928 -25195355 69603194 71801068 27259746 -96212811 96031961 27890165 76618755 -64261689 -99095784 13417302 -95521354 -29591717 -34815155 -93743823 -93393132 -...
output:
49999995.0818661941 49999995.9004091124 49999995.3149217014 49999995.3054674002 49999994.5577050093 49999996.4862814266 49999994.6940732430 49999995.1368903976 49999995.7255437915 49999995.4937630891 49999997.2567733076 49999994.7944017604 49999994.9287077410 49999995.7829386723 49999994.9440986489 ...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 1615ms
memory: 29464kb
input:
100000 28442101 95869943 64560849 76366848 -85662377 51594149 95580169 -29401185 -40181553 -91572058 67627360 -73665047 82527643 56472888 29700208 95487675 87983116 -47528622 62992785 77665358 -2222699 99975284 -64132427 76726992 -76047272 64936977 87016456 49276108 95274227 30377974 -62944509 -7770...
output:
49999994.8309710390 49999995.5183788592 49999994.9251787021 49999995.5234946922 49999994.8275525085 49999994.6394857935 49999994.8678172358 49999996.4713342653 49999995.0233866907 49999995.4033335249 49999994.9916431116 49999994.9030463941 49999995.6710114568 49999995.2659545375 49999995.3312548597 ...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 1530ms
memory: 32732kb
input:
100000 66926611 74302272 -39804607 -91736532 -31850108 94792239 -94396583 -33004302 -57766222 81627580 -80246004 59670576 74979879 -66166588 37426246 -92732280 -40775354 -91309200 99674197 8065507 94244794 -33435279 -24613128 -96923641 28694420 -95794726 97637671 -21607478 -49066338 -87134919 612455...
output:
49999995.7715908148 49999995.4357772327 49999996.4043741883 49999994.8179789327 49999997.2285060446 49999995.8582851484 49999995.0825320438 49999994.5402301618 49999994.6179780847 49999995.4909426205 49999995.5851056779 49999994.7581311457 49999997.0426210118 49999994.9688381011 49999995.9953611581 ...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 1534ms
memory: 30468kb
input:
100000 31516589 94903656 70239724 71178504 -57719682 81660501 73612201 67684871 82391354 -56671542 72801723 -68555878 26893692 -96315770 -83483265 55050367 87478845 -48450493 -85026739 52635096 -26511823 96421583 95776532 -28755096 88242174 -47045913 77725402 -62918677 -14344932 98965762 -25054341 -...
output:
49999995.1416609891 49999995.1742068688 49999995.8579723495 49999997.1304232285 49999995.6565237637 49999995.2441420847 49999995.3516391511 49999994.6824236612 49999995.6391572192 49999995.6166996073 49999995.0758054910 49999997.0231123448 49999994.7090391855 49999996.2098523259 49999995.4048886005 ...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 1741ms
memory: 30824kb
input:
100000 -77953946 -62635297 -97003745 24295529 -95559516 -29468254 -37774475 -92590972 -78235761 62282941 24449261 96965108 -32126090 -94699061 -90361637 -42834246 -15234257 -98832767 -67393723 -73878858 -77089954 63695658 -87433336 -48532575 45142341 -89230981 80543145 -59268883 99006350 -14062036 -...
output:
49999994.8800609984 49999995.6036443484 49999995.4473164310 49999994.8234286120 49999994.7814365927 49999994.9757974577 49999994.9918332584 49999996.4288837310 49999995.4920812346 49999996.1784076709 49999995.1575361160 49999994.5227592685 49999995.0962231795 49999994.7197688141 49999995.0631763546 ...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 2733ms
memory: 31084kb
input:
100000 -14994761 -98790003 -52791662 84821895 87513045 48313812 19785427 97922747 98912337 -14130131 -4520530 -99837938 93690283 34834919 99547007 8570663 86380533 -50241768 -46722739 88350371 69496929 -71791216 -85910197 -51161960 5199588 99844597 11410781 -99298438 -99814172 5122831 99748209 57815...
output:
49950309.3056237988 49950587.9321183814 49950271.2551974819 49950284.2250954475 49950441.6709376118 49950141.2846822302 49950288.3766497255 49950469.2183907807 49950744.1464028661 49950688.2312025683 49950339.5676553654 49950216.2988869351 49950092.5740196349 49950416.5313250064 49950177.6632704128 ...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 2292ms
memory: 31912kb
input:
100000 87107311 49115334 -98093001 -19436093 86159431 -50759733 -90576186 -42378693 99725385 7405849 -93030414 -36678893 7164898 99742981 88908273 -45774642 -87848897 47776244 98650729 -16371688 -13992770 99016167 -36675953 93031566 -28482368 95857989 -38312130 -92369793 86372731 50395931 -50997291 ...
output:
49999995.7797225483 49999994.6245876048 49999998.3509637771 49999995.5115784139 49999995.0933498618 49999994.8836178114 49999997.9886450427 49999996.2295945657 49999998.0441679807 49999995.8618392846 49999996.7392814076 49999996.2061849361 49999996.8127210472 49999997.1296632283 49999998.4672184243 ...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 2687ms
memory: 30668kb
input:
100000 87353211 -48676647 78574311 -61855286 1089525 99994063 -99999914 -125343 -79940915 -60078697 97608574 -21738565 -99570798 9254977 -57082835 -82106930 77989099 62591525 -36640991 -93045345 -82795 -99999957 99857762 5331654 91364668 40650900 -89488349 -44629962 24733984 96892872 87543386 483337...
output:
49999998.4114884826 49999997.9731765491 49999997.2725407361 49999998.4609082007 49999994.7726248631 49999996.2591437467 49999997.4391602003 49999997.4595152484 49999994.9463549853 49999996.9207552870 49999997.9735086032 49999996.5709999078 49999996.1017815344 49999997.6848153128 49999995.7377748194 ...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 3031ms
memory: 28944kb
input:
100000 -95807142 28504127 58593535 -80943524 -99766431 5986168 93220087 -35989826 3645498 -99841657 69856363 -71476864 6430623 99747801 99074166 -13444307 25226151 96750874 -99820804 -4584947 80958147 58644185 99854141 3972407 93127038 36267563 83656508 -54710699 73943321 -67286687 22540877 -9736065...
output:
49951675.8764737743 49951660.7759727305 49951740.4114056055 49951465.4638304028 49950200.2577471236 49950954.5130789854 49951162.3204078494 49950823.9987229996 49951011.4364624367 49951169.7614416876 49950251.9870868726 49950960.8967498478 49951548.7213694641 49950976.9117757239 49950703.5493174638 ...
result:
ok 100000 numbers
Test #17:
score: 0
Accepted
time: 3487ms
memory: 28820kb
input:
100000 -18866705 98167110 96374803 -26445175 -90527905 42406852 93525949 35171769 -99675297 7020406 -99946706 -2220134 31631621 -94776631 -46384811 88576816 -2476324 99950315 69306249 -72003171 -30910251 -95067123 85457008 51882654 82372940 -56613508 6032490 99757677 99488049 -9473775 97295326 22667...
output:
49950435.4342463168 49950523.6429177893 49951727.0368673848 49950791.7197091727 49952062.1846697600 49951220.3037158485 49950723.9434544286 49951030.2751690404 49951362.7755594238 49951028.0508876230 49951744.1141123088 49951224.7437644795 49952317.4008079955 49951224.1601771633 49951151.4789893492 ...
result:
ok 100000 numbers
Test #18:
score: 0
Accepted
time: 3003ms
memory: 31080kb
input:
100000 -94544376 30244008 -5524553 -99134196 64736465 74935295 -10781223 -98537615 -27540414 96110283 94534101 -30554453 -49000527 -87040163 -70553197 70503800 90093758 -41264733 51497088 84792240 -50688507 -85177162 95747827 28411115 -85773541 -50275968 -34190721 93830767 -42611828 90282250 -315970...
output:
49503286.6071341862 49503940.1660004199 49500902.0574530688 49502328.8001762668 49504050.8899425749 49503864.7113224403 49502762.9502231849 49505338.4543824051 49503140.1828940405 49508220.5136476464 49506314.7348970712 49508005.3967640638 49501854.4901581556 49506908.0257155500 49503251.9579029106 ...
result:
ok 100000 numbers
Test #19:
score: 0
Accepted
time: 3266ms
memory: 31564kb
input:
100000 -72724429 68353169 -23398454 96972722 98697156 15295066 -50053634 86257978 95660227 -25689933 -98427638 12257835 -95720479 25986032 99360720 -9958797 -34453585 -93167496 97657115 21470158 -61854668 77939046 -78666489 60608092 99656422 -4271277 37176490 92108858 92266107 -36908241 84966021 -52...
output:
49505232.2522462104 49505902.9530284100 49506391.3517989339 49501384.8619998096 49501974.5375367875 49503956.2921274886 49506260.8484404916 49507848.9578431358 49507844.1977249836 49507646.9159879079 49505334.2111403260 49504283.4305713325 49503897.6784182638 49506239.9631956961 49506420.6701118899 ...
result:
ok 100000 numbers
Test #20:
score: 0
Accepted
time: 3498ms
memory: 30288kb
input:
100000 -98189095 15784434 89982407 42479712 -98538151 10378719 48446566 -87123427 90936804 -40512021 67828507 72315413 -19102654 97627943 -40632682 -90422395 -71928032 68028353 59463681 -80194272 -61979681 77927882 -89859188 -41650204 -40753972 -90873220 -31802337 -94326140 29901118 94629634 8981744...
output:
49501432.7022043765 49504111.9000156403 49506914.0037283619 49504020.3841625653 49500748.1808290217 49509533.2816175665 49504423.6514928474 49503519.1264973206 49507687.1662349230 49501887.8451572912 49501129.4738505480 49506066.7849481715 49503294.6517206474 49500496.9255725455 49503260.6522218648 ...
result:
ok 100000 numbers
Test #21:
score: 0
Accepted
time: 3075ms
memory: 30248kb
input:
100000 74210313 -66772568 -82118759 55744795 -40558611 -90552265 -80801514 58093666 -87555090 46582002 -96330979 24086781 39402894 91628283 56594773 -82141487 39313600 91784698 89239441 43417687 -95774367 28264902 32961837 93669012 -85873036 -51077556 -27532569 -96083438 82705246 -55505999 -22508180...
output:
49506572.9114001307 49507188.3698279338 49504015.5868492220 49502226.2551336864 49511712.3791654684 49508088.3725657533 49508038.4721606655 49511153.9459437267 49503445.7644251330 49505408.2422356359 49501120.2191417217 49504635.7946901289 49501929.8603164177 49500674.3593257255 49508683.1372701624 ...
result:
ok 100000 numbers
Test #22:
score: 0
Accepted
time: 3002ms
memory: 30524kb
input:
100000 -71207198 55424979 -79825607 -56036270 -83654833 37345395 -91097555 -17973035 -79663519 53088655 40943861 -91076400 84688501 31061641 -96431516 -1566452 -89205053 17120308 66023621 -67658770 -85253305 44553904 -95493219 -8941382 -79301859 45970085 -27319544 -90541866 -90379686 -10409784 -8376...
output:
45036750.1372239081 45027842.8818135627 45013570.7649708689 45012430.8467586790 45008268.5080020579 45035953.6251026984 45011940.3266864407 45033497.6378687234 45035993.0317809311 45018438.5524730843 45010458.6109155562 45008354.7259051865 45032420.0671344288 45019612.3304007581 45010086.5286969899 ...
result:
ok 100000 numbers
Test #23:
score: 0
Accepted
time: 2943ms
memory: 29900kb
input:
100000 38905528 81237636 -87968422 -27436984 9608199 91019553 78087433 -61515160 -93465529 27267558 13655649 -92011700 -4844144 -90101777 -76856347 -55299593 7037669 95820739 73512631 -55423174 66171160 -69809341 -38015506 -91878674 92573512 18160315 -89558982 43574979 41250811 89067345 90892069 312...
output:
45035187.3884272974 45009163.6065221989 45033436.3931769841 45019451.0239726607 45022200.7504397128 45014848.4584343798 45024066.2168218609 45004916.9090575680 45009051.6157130487 45011633.8119250022 45006265.9086879572 45025389.7773992522 45018143.2059153051 45004427.2401311876 45017652.0731754354 ...
result:
ok 100000 numbers
Test #24:
score: 0
Accepted
time: 2999ms
memory: 29892kb
input:
100000 73858871 59646768 74771059 50581404 69886208 66567485 -98824001 3209940 71195346 65729342 -31147238 89170502 -93247841 -18314860 25371727 94636356 96922565 192144 11319923 -96984253 -90534277 -37798172 92579912 22026541 -85805605 34201581 -34434706 84998535 28174675 -86301411 18885420 9491316...
output:
45004913.3664170944 45049419.1160457681 45013923.5129688185 45018139.6488505513 45036905.8127368647 45014915.9261846652 45021998.4164936971 45005546.4190510395 45013393.3187403220 45031474.2617547221 45023802.2902519771 45024466.4821735796 45028156.9922565102 45028587.9272050929 45021843.4432482475 ...
result:
ok 100000 numbers
Test #25:
score: 0
Accepted
time: 2642ms
memory: 30260kb
input:
100000 6192364 97854354 -26396072 -87670473 -15829494 95984810 29977494 -87073709 85322761 44933323 -10724758 96451337 25075242 -88807937 88653656 -28596396 -7234959 97007100 -98015205 5615321 -46753278 -86423176 -84626507 -46187913 58215823 -70504834 88062585 26935126 79507695 56070039 -81885399 -4...
output:
45007894.8356611436 45013616.1135625201 45048543.6061462096 45027729.0330647820 45013317.4985193662 45020005.9202678623 45013214.4532615194 45017977.1928253231 45015065.2213866702 45019880.1661492955 45029719.3585011695 45018055.1420109609 45027958.6147321080 45032293.0370835621 45023771.4683760886 ...
result:
ok 100000 numbers
Test #26:
score: 0
Accepted
time: 2966ms
memory: 29080kb
input:
100000 -56925997 -77019489 93686323 23015852 -96967479 14925388 -69298767 71247873 -89975226 -39629378 -81202105 -57862266 -30611438 -91102049 69779237 60415278 85454036 38912399 -23494246 -94997385 11333990 -97239874 26776076 95709458 7400584 -95188065 94132228 33609835 31334391 -91724795 15440367 ...
output:
45031230.0083619330 45031012.6837546242 45051159.9267532924 45057523.9439006005 45021248.9383935129 45034531.5222572914 45010861.9044016793 45036940.6662583623 45011332.8873037123 45014214.3833544224 45031679.2282824025 45012785.3672063191 45001127.1071561677 45030055.9623051226 45008553.3961223973 ...
result:
ok 100000 numbers
Test #27:
score: 0
Accepted
time: 3415ms
memory: 28868kb
input:
100000 86473583 -50222687 87983523 47527871 50172327 -86502810 -50052528 -86572186 -81465580 57994464 99757942 6953600 -89115446 45369999 -98572877 16834073 86724085 -49788872 -72244940 -69142374 95384011 -30031466 31730815 -94832244 -96383253 26650854 70233115 71185027 38343247 92356888 -76013019 6...
output:
49999997.4571804445 49999998.4627793917 49999997.1012831272 49999996.8661267463 49999998.6305340222 49999998.5050832598 49999996.2101661278 49999998.6642196312 49999997.4219625144 49999996.6097953529 49999997.2465502875 49999997.5784507015 49999997.7963023625 49999996.7176688653 49999998.5363129047 ...
result:
ok 100000 numbers
Test #28:
score: 0
Accepted
time: 3085ms
memory: 29448kb
input:
100000 96098382 27660424 96993975 -24334494 98858570 15065921 -70174372 71242940 59401282 80445550 -34968800 -93686616 -45576276 89010123 -93157321 36355368 -98590008 -16733454 29170468 95650836 81074291 -58540220 92315133 -38443648 88517611 -46525596 99591182 -9033025 17031645 -98538935 -76791060 -...
output:
49999997.2281586992 49999997.3025419674 49999996.6710480845 49999996.7132198505 49999998.7399825526 50000000.5315516597 49999998.0506880440 49999998.9604979678 49999996.7553592107 49999997.1424608377 49999998.7725008478 49999997.5903435250 49999998.3012374512 49999999.1442935974 49999997.1038764379 ...
result:
ok 100000 numbers
Test #29:
score: 0
Accepted
time: 3097ms
memory: 29076kb
input:
100000 98649054 -16381761 -99891340 -4660392 85079131 -52550367 98751502 -15752448 38325930 -92364069 16772724 98583333 75122377 66004758 95139156 30798377 -24102560 97051870 89328512 44949025 -83521481 -54992370 -22923261 97337161 -49154851 87085012 67965351 -73353320 -79586737 60547083 44791227 -8...
output:
49999996.8124151280 49999996.7088924272 49999997.6572201374 49999997.0251825251 49999997.5584498117 49999997.9676561649 49999998.1619126608 49999996.5120547797 49999998.4548825087 49999998.2111204075 49999998.4433880100 49999997.0462427771 49999997.1573696596 49999997.0651829779 49999995.5362256137 ...
result:
ok 100000 numbers
Test #30:
score: 0
Accepted
time: 3078ms
memory: 31192kb
input:
100000 7197545 -99740639 39789850 91742935 -44563738 -89521349 92588284 -37781069 89874957 43846213 -97082384 23979340 52035210 85395169 87881876 -47715555 -25428031 -96713047 6688701 99776051 31394586 94944081 66622083 -74575443 81096253 -58509804 -98223145 18767345 10583592 -99438356 -97020186 -24...
output:
49999997.0242636219 49999996.4351697949 49999997.5472669976 49999996.4184565740 49999998.7878663446 49999997.8148425174 49999998.1209330582 49999996.1151277519 49999996.8872683443 49999996.1102720128 49999997.6365981970 49999998.0198364671 49999998.7855395929 49999998.6437689914 49999996.0682024158 ...
result:
ok 100000 numbers
Test #31:
score: 0
Accepted
time: 3083ms
memory: 30700kb
input:
100000 48053189 87697724 -99230647 -12380496 71228034 -70189504 -99862038 -5250874 -92715593 -37467545 26308785 -96477183 91137520 41157649 86371053 50398812 -99541893 -9560913 -96837592 24949526 -28842311 95750301 -99906431 4324846 32704032 -94501032 -98983846 14219579 -98402231 17804504 42162900 9...
output:
49999996.0831308637 49999996.4655374477 49999998.4432053235 49999995.6520978698 49999998.1852533965 49999998.4148445374 49999999.0013581327 49999997.2984745646 49999997.1851978291 49999999.0488718601 49999997.2643068664 49999996.6181674743 49999996.5855972062 49999997.8302103618 49999997.6317784903 ...
result:
ok 100000 numbers
Test #32:
score: 0
Accepted
time: 3980ms
memory: 30432kb
input:
100000 -23951830 97020265 -79900659 60056128 -83964098 54143803 97074821 23809857 61007903 79212713 -45094976 89223718 -89377964 44681664 -98513176 -17056240 -27426886 -96062608 56189487 82666265 18047227 -98345883 -99936265 1286532 18608822 98231586 -56949101 82157764 99503767 -8898358 52721687 -84...
output:
49951674.1879358572 49951419.3102471677 49951190.6025995812 49951412.5821994062 49951643.3201369413 49952981.5404847637 49951531.5661155800 49950744.7078593344 49951759.6741204799 49952147.6803641543 49950940.6456706008 49951560.3948296950 49951096.6605874512 49952163.0136613007 49952791.2038600241 ...
result:
ok 100000 numbers
Test #33:
score: -100
Time Limit Exceeded
input:
100000 -82922797 55795521 98806631 15264719 27227855 96151671 90640250 -42064680 97570886 21814297 11561464 99312553 -63044255 -77522636 75253645 65715048 -46471655 -88525692 -74788283 66304581 59047518 -80664807 99509005 9753002 6599999 -99699054 -57520499 -81692754 -94724230 -32037998 -91266303 -4...
output:
49951008.8752196898 49952120.1151771756 49951313.8975321696 49951522.6341236542 49951493.4673221721 49951417.8990497972 49951239.5873102925 49950786.0584494720 49951126.6194569922 49951635.2534672451 49951599.4435538328 49952120.2602650853 49951396.9518224784 49951843.5781770995 49951084.2984792269 ...