QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#444835 | #8525. Mercenaries | ucup-team1198# | WA | 3924ms | 359884kb | C++20 | 4.8kb | 2024-06-15 21:34:42 | 2024-06-15 21:34:43 |
Judging History
answer
#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
struct Vector {
int x;
int y;
Vector(int x = 0, int y = 0): x(x), y(y) {}
};
Vector operator-(const Vector& a, const Vector& b) {
return {a.x - b.x, a.y - b.y};
}
Vector operator+(const Vector& a, const Vector& b) {
return {a.x + b.x, a.y + b.y};
}
int operator*(const Vector& a, const Vector& b) {
return a.x * b.x + a.y * b.y;
}
int operator%(const Vector& a, const Vector& b) {
return a.x * b.y - a.y * b.x;
}
int sgn(const Vector& a, const Vector& b) {
__int128 res = a.x * b.y - a.y * b.x;
if (res < 0) return -1;
if (res == 0) return 0;
return 1;
}
bool operator<(const Vector& a, const Vector& b) {
if (a.x == b.x) {
return a.y > b.y;
}
return a.x < b.x;
}
vector<Vector> operator+(const vector<Vector>& a, const vector<Vector>& b) {
vector<Vector> res;
res.push_back(a[0] + b[0]);
int ia = 1, ib = 1;
while (ia < (int)a.size() || ib < (int)b.size()) {
if (ia == (int)a.size()) {
res.push_back(res.back() + b[ib] - b[ib - 1]);
++ib;
} else if (ib == (int)b.size()) {
res.push_back(res.back() + a[ia] - a[ia - 1]);
++ia;
} else if ((a[ia] - a[ia - 1]) % (b[ib] - b[ib - 1]) < 0) {
res.push_back(res.back() + a[ia] - a[ia - 1]);
++ia;
} else {
res.push_back(res.back() + b[ib] - b[ib - 1]);
++ib;
}
}
return res;
}
vector<Vector> hull_sorted(const vector<Vector>& a) {
vector<Vector> st;
int sz = 0;
for (Vector p : a) {
while (sz >= 2 && sgn((p - st[sz - 1]), (st[sz - 1] - st[sz - 2])) <= 0) {
st.pop_back();
--sz;
}
st.push_back(p);
++sz;
}
return st;
}
vector<Vector> unite(const vector<Vector>& a, const vector<Vector>& b) {
vector<Vector> c;
merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
return hull_sorted(c);
}
const int MAXN = 2e5 + 100;
Vector hero[MAXN];
vector<Vector> shop[MAXN];
vector<Vector> tr_shop[MAXN * 4];
vector<Vector> tr_hero[MAXN * 4];
void build(int v, int vl, int vr) {
if (vr - vl == 1) {
sort(shop[vl].begin(), shop[vl].end());
tr_shop[v] = hull_sorted(shop[vl]);
vector<Vector> h = {hero[vl]};
tr_hero[v] = h + tr_shop[v];
return;
}
int vm = (vl + vr) / 2;
build(v * 2, vl, vm);
build(v * 2 + 1, vm, vr);
tr_shop[v] = tr_shop[v * 2] + tr_shop[v * 2 + 1];
tr_hero[v] = unite(tr_hero[2 * v] + tr_shop[2 * v + 1], tr_hero[2 * v + 1]);
}
int norm(int x, int n) {
return x >= n ? x - n : x;
}
int get_tan(const Vector& v, const vector<Vector>& p) {
int i = 0;
int k = 0;
int n = p.size();
while ((1 << k) < n) ++k;
while (k >= 0) {
int i1 = norm((i + (1 << k)), n);
int i2 = (i - (1 << k) + 2 * n) % n;
if (v * p[i1] > v * p[i]) i = i1;
if (v * p[i2] > v * p[i]) i = i2;
--k;
}
return p[i] * v;
}
int get_pref(int v, int vl, int vr, int r, const Vector& dir) {
if (r <= vl) return 0;
if (r >= vr) {
return get_tan(dir, tr_shop[v]);
}
int vm = (vl + vr) / 2;
int res1 = get_pref(v * 2, vl, vm, r, dir);
int res2 = get_pref(v * 2 + 1, vm, vr, r, dir);
return res1 + res2;
}
int get_last(int v, int vl, int vr, int r, const Vector& dir, int c) {
if (r <= vl || (r >= vr && get_tan(dir, tr_hero[v]) < c)) return -1;
if (vr - vl == 1) return vl;
/// cerr << v << " " << vl << " " << vr << endl;
int vm = (vl + vr) / 2;
int res = get_last(v * 2 + 1, vm, vr, r, dir, c);
if (res != -1) return res;
c -= get_pref(v * 2 + 1, vm, vr, r, dir);
return get_last(v * 2, vl, vm, r, dir, c);
}
istream& operator>>(istream& in, Vector& v) {
in >> v.x >> v.y;
return in;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n - 1; ++i) {
cin >> hero[i];
int sz;
cin >> sz;
shop[i].resize(sz);
for (Vector& v : shop[i]) {
cin >> v;
}
}
cin >> hero[n - 1];
build(1, 0, n - 1);
/// cerr << "built" << endl;
int q;
cin >> q;
while (q--) {
int ind, c;
Vector dir;
cin >> ind >> dir >> c;
--ind;
/// cerr << ind << " " << c << endl;
if (dir * hero[ind] >= c) {
cout << ind + 1 << "\n";
continue;
}
/// cerr << "start" << endl;
int res = get_last(1, 0, n - 1, ind, dir, c);
/// cerr << "end" << endl;
if (res == -1) {
cout << "-1\n";
} else {
cout << res + 1 << "\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 8508kb
input:
3 1 1 2 1 2 1 2 3 2 5 1 5 4 3 3 4 5 1 1 2 4 5 12 1 1 1 1 2 1 1 1 3 1 1 1 3 1 1 9 3 2 2 20 3 1 2 18 3 1 2 19 3 1 2 20 3 0 1 8 2 1 0 4 2 1 0 3 2 1 0 2
output:
1 2 3 3 2 2 1 -1 1 -1 2 2
result:
ok 12 numbers
Test #2:
score: 0
Accepted
time: 3ms
memory: 7360kb
input:
2 47 11 1 98 25 9 90 10 1 32 28 1811 2 17 44 4114 1 36 88 2661 2 79 33 3681 1 53 26 2778 2 59 20 2332 2 63 45 4616 2 72 11 10835 1 13 28 919 2 16 59 4445
output:
1 -1 -1 2 -1 1 2 1 1 2
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 7092kb
input:
3 87 42 5 69 12 82 79 10 88 45 51 40 3 18 6 5 73 100 58 41 40 88 54 5 40 98 31 63 100 3 32 13 1811 1 51 21 5318 1 32 5 2994 2 77 51 19184 2 78 60 1763 1 10 1 913 1 22 51 4057 1 2 5 385 2 50 15 989 2 65 53 1488 1 49 82 7708 2 33 90 1133 1 23 33 3388 1 92 36 9516 3 39 61 10014 2 43 55 1103 2 48 38 127...
output:
3 1 1 1 2 -1 -1 -1 2 2 -1 2 -1 1 2 2 -1 3 2 2 3 1 1 1 -1 1 1 1 3 1 -1 1 -1 1 2 1 2 1 1 1 1 1 -1 1 -1 -1 1 1 -1 -1 1 1 2 1 1 -1 2 -1 1 1 1 1 3 1 2 3 2 2 1 1 -1 1 1 3 1 1 1 3 2 1 1 2 1 2 1 2 1 -1 -1 -1 1 2 1 1 -1 -1 1 3 2 2
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 144ms
memory: 15136kb
input:
2 309248041 338995438 500000 1235 4866 1931 3652 1921 258 545 587 3001 542 3074 1694 4944 206 3217 3135 2388 4791 1890 3281 3840 4614 4491 1339 4660 1708 2225 3199 736 1306 4175 4652 906 3509 2571 1578 50 981 402 4975 2730 2198 4546 3120 40 815 2492 518 2102 2651 1018 3996 1764 808 3934 4312 1981 40...
output:
2 1 -1 2 2 2 1 1 2 -1 2 2 1 1 2 1 2 2 1 2 2 1 -1 -1 1 -1 2 -1 1 2 1 1 1 1 -1 1 -1 -1 -1 1 2 2 1 1 1 2 -1 -1 1 -1 1 2 -1 1 2 1 2 2 -1 2 1 2 2 -1 2 2 -1 2 1 2 1 -1 -1 1 1 -1 2 1 2 2 1 1 1 1 2 2 -1 -1 1 2 2 -1 2 -1 -1 -1 1 2 1 1 2 2 1 -1 -1 2 2 2 1 -1 1 2 2 -1 1 -1 -1 -1 1 2 1 2 1 -1 -1 1 2 2 -1 2 2 2 ...
result:
ok 200000 numbers
Test #5:
score: 0
Accepted
time: 303ms
memory: 154552kb
input:
200000 999999511 993051669 2 5000 5000 5000 5000 1000000000 1000000000 3 5000 5000 5000 5000 5000 5000 995868520 999999999 2 5000 5000 5000 5000 660478427 999992996 3 5000 5000 5000 5000 5000 5000 999999979 999999998 2 5000 5000 5000 5000 861450412 989532141 3 5000 5000 5000 5000 5000 5000 949861679...
output:
145800 198491 112658 29436 38091 122582 7727 87686 192036 97288 60184 836 39235 158331 121422 117149 189664 153018 181334 56603 69911 173097 165342 124250 103223 110099 177817 11459 37052 28918 57236 143793 19234 10313 75590 6597 18202 176357 102394 179685 5171 162359 72023 56758 88764 17257 100583 ...
result:
ok 200000 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 7640kb
input:
20 1538 3628 4 2423 3790 3127 3961 2614 3582 2016 4789 1441 276 3 2518 253 4221 265 3236 2574 1668 3370 4 4489 3533 4501 2177 1067 2337 2765 1480 1179 1926 3 4922 2537 1477 653 325 444 3964 2924 2 3415 4463 822 3257 210 4068 2 1969 167 1978 3712 2067 540 4 1560 2211 4050 4196 442 2279 442 2448 2962 ...
output:
5 14 5 1 2 3 6 -1 8 7 2 11 1 8 8 3 3 13 4 5
result:
ok 20 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 8424kb
input:
66 121 3727 2 1379 2036 975 1594 205 708 2 523 2978 176 2924 2528 440 4 3182 2078 1340 2166 1563 447 1076 157 3242 2859 5 2029 4660 2789 1593 4534 4137 921 3966 3440 1964 1503 3975 3 1354 3815 825 4981 1710 2692 858 2524 3 3395 3523 2184 4115 4043 3518 2610 731 3 3735 2799 442 1348 3101 2847 4306 14...
output:
9 12 20 -1 3 18 23 2 4 48 13 -1 8 38 8 28 7 1 8 51 4 9 10 10 3 24 14 5 19 2 33 3 45 5 4 29 5 23 24 36 24 -1 9 4 26 1 2 1 46 37 8 2 20 2 1 27 26 41 5 32 3 37 -1 7 43 2
result:
ok 66 numbers
Test #8:
score: 0
Accepted
time: 3ms
memory: 8044kb
input:
200 2768 3191 1 482 2676 4032 1626 1 1313 472 117 4314 3 1745 3269 1723 1603 1307 2675 2553 172 5 1678 868 246 2764 3746 3346 3650 317 3675 3877 2425 2618 2 1883 4174 4213 1781 3099 3645 1 4652 2962 1910 1338 3 4530 2328 2576 3373 3 1145 1887 1331 4 459 736 139 3184 550 31 740 3134 3488 2965 3 2097 ...
output:
57 85 59 36 24 39 5 4 81 49 23 107 104 39 62 49 3 156 25 64 13 92 16 62 20 104 13 26 66 61 109 56 1 32 7 37 14 9 10 136 20 7 2 129 149 109 29 15 51 18 80 107 6 20 50 27 111 -1 115 16 10 88 21 12 88 1 2 31 72 10 67 68 5 6 1 80 120 73 187 26 17 2 64 125 -1 43 4 10 72 13 129 45 118 54 27 56 100 56 27 3...
result:
ok 200 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 8000kb
input:
666 2648 877 2 170 1622 4953 3255 18 2631 2 2355 1545 3734 1505 724 216 1 1944 1090 3733 2918 3 3393 1081 3478 4932 2001 501 3399 1829 3 4189 4125 1957 1754 2904 3622 4643 554 4 229 4356 3777 1315 4848 2584 1232 2718 4096 1924 2 892 1180 3500 2905 1759 1274 4 3950 1096 1779 2159 1617 1856 3182 2679 ...
output:
466 198 247 228 66 306 101 147 11 480 35 354 59 225 76 20 314 84 272 2 315 13 6 4 212 430 28 290 339 121 125 4 21 362 254 19 77 456 69 27 62 6 269 100 68 4 396 1 58 377 203 100 94 162 188 151 48 4 377 277 242 274 217 167 45 24 116 291 263 305 112 183 225 5 107 120 210 56 50 140 4 192 165 250 303 77 ...
result:
ok 666 numbers
Test #10:
score: 0
Accepted
time: 12ms
memory: 9188kb
input:
2000 2883 1742 3 281 1763 9 3931 3350 1572 1611 462 3 983 1286 1874 1928 4279 857 3773 1341 2 3861 4264 733 4060 1220 1451 3 2753 624 4520 2881 2051 1614 1406 2742 5 2857 2152 4349 495 3552 1319 4118 4269 3286 2235 4028 1138 4 2209 4188 1788 4226 517 2932 4067 3746 3105 2345 2 731 2039 1927 1275 137...
output:
1 210 42 101 386 26 68 202 806 352 362 29 559 52 1334 741 260 565 1041 85 220 67 448 194 1110 179 843 625 453 1055 641 691 79 145 869 10 40 8 60 134 1108 179 560 773 1748 452 469 1165 515 456 602 366 781 15 5 269 459 42 509 1046 339 1064 923 944 84 76 499 -1 1345 1051 44 2 1406 680 1726 326 32 96 85...
result:
ok 2000 numbers
Test #11:
score: 0
Accepted
time: 34ms
memory: 13232kb
input:
6666 2741 2461 3 526 4139 3060 2030 2766 3316 653 3631 1 4366 67 2628 3849 2 2449 2607 1617 68 3001 126 1 4561 4505 3166 3358 3 4322 1581 957 756 865 3540 1442 2226 4 4137 2789 2636 3371 3383 60 620 2488 550 3026 5 1285 3936 4074 4144 3933 3572 825 2255 55 796 4544 1791 3 1459 863 4284 3153 1674 122...
output:
46 1772 1912 2973 15 5358 3822 649 679 4265 1819 3808 783 1759 1426 2865 1820 11 168 209 4207 3606 1234 4049 576 1052 1514 86 191 712 4475 2262 223 1513 3483 3719 5287 4028 200 2063 241 1217 3043 622 955 5463 1806 337 855 2275 2962 164 3955 1673 353 2999 4622 2701 601 1999 933 35 2004 3380 64 776 27...
result:
ok 6666 numbers
Test #12:
score: 0
Accepted
time: 153ms
memory: 29132kb
input:
20000 1186 1182 1 2552 75 370 1750 2 1657 2841 3265 719 3481 2197 2 4047 16 277 1224 593 97 4 358 4602 1995 1679 1888 4757 4297 2320 3187 3062 2 2394 2756 3744 3166 467 261 3 3385 2572 4595 719 3514 1870 178 3985 4 1004 1799 4259 2920 1155 2664 4064 3732 385 2278 2 1784 4561 1022 1281 3907 2706 1 39...
output:
629 10461 7163 711 6127 3895 1990 1492 3117 2779 3930 428 10729 938 1012 541 6697 3517 4567 6669 285 10601 15453 11721 2 633 535 288 13293 15510 13541 1550 6895 6138 5565 6672 93 1621 6958 4345 4669 6546 11999 74 4152 7192 3334 2423 1982 1884 1956 3630 4614 1777 1826 6986 9 2318 8064 303 3082 1287 1...
result:
ok 20000 numbers
Test #13:
score: 0
Accepted
time: 393ms
memory: 54172kb
input:
40000 1322 4123 3 1729 4107 1325 1826 756 1338 2281 2223 4 3251 2045 4210 3298 3405 2626 2449 2539 332 4779 2 4329 2666 4605 253 501 2829 3 2908 2017 3694 4704 3794 3259 2231 3518 3 984 1800 2861 888 1137 4675 16 2796 5 3690 143 3763 3138 663 298 174 2769 3953 1526 1320 1584 2 3472 4857 1781 4871 39...
output:
117 10439 9881 3959 6978 234 11142 6493 28076 4122 9986 11628 20104 10580 20548 21044 2006 7256 14386 17260 7249 2969 18038 3722 1976 1080 19587 1804 108 2722 1370 554 2415 13413 4430 4743 1490 21 15752 14857 31955 1250 10259 10460 1775 996 51 13148 13819 22536 2861 2321 69 10517 4007 10082 13384 65...
result:
ok 40000 numbers
Test #14:
score: 0
Accepted
time: 737ms
memory: 84904kb
input:
66666 3910 403 2 475 1131 939 2976 3588 2717 3 4367 2516 4737 4629 351 2278 879 4121 1 4665 4982 1229 3257 3 4774 412 2628 3043 2537 4632 4102 764 4 365 1999 1340 1043 725 184 1366 464 1632 462 1 3678 1459 1472 3921 2 2218 3124 1193 4188 587 4637 3 663 2801 3365 1486 4024 2027 464 4849 2 3627 726 18...
output:
18005 6802 4402 63081 12216 1997 3852 2251 25870 25581 25907 172 21566 7609 432 11729 6583 7984 5659 8279 2295 27118 11619 4499 18976 2789 64962 7114 17828 4100 9093 2201 164 25433 799 9329 1573 5677 1802 6594 16903 3261 10135 4868 1878 8830 43109 33459 478 18129 21607 24469 102 1169 18060 11070 145...
result:
ok 66666 numbers
Test #15:
score: 0
Accepted
time: 1221ms
memory: 119908kb
input:
100000 2766 3928 1 801 4090 1696 1887 2 2478 338 4886 2028 4449 473 2 4009 2510 587 962 3272 2216 2 1422 457 2248 2264 1634 2781 1 463 1296 292 433 4 406 4396 99 4408 64 1583 2977 4428 2628 1270 2 2431 4144 2898 2133 1412 4349 2 2756 3515 1551 3118 2461 1056 1 3027 4519 3257 940 2 1241 1252 4920 465...
output:
71 44948 26956 58728 15513 11202 23070 1708 936 2159 10979 37052 26887 7507 24943 1182 12837 6822 55436 8472 45797 40278 23445 1702 5051 50219 7096 1063 18284 379 52305 25792 17832 12078 11885 53278 8544 1148 6362 10594 13108 66927 44308 65930 74953 13065 1153 3085 443 9498 12671 10554 29519 43697 3...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 3022ms
memory: 242472kb
input:
200000 870 4638 6 4716 1571 845 599 943 4354 4102 2994 4706 3121 1579 4190 4305 2436 2 2767 1501 3629 98 3824 1262 1 2748 2558 1723 166 3 4457 4290 1253 3994 4266 4934 2021 1195 1 2736 2682 2407 484 3 1531 3959 3257 2154 123 1106 2441 674 1 2450 2914 3057 3536 3 1533 1051 1507 2518 3773 2867 3622 15...
output:
157843 25378 57229 10046 64593 20854 163253 59732 56538 978 2512 108129 2903 69944 5488 98723 14617 165726 23353 409 57829 79874 123834 4583 8613 3554 33478 12378 19599 94577 5555 76752 95569 1701 16813 181 12645 2668 50296 58364 79228 918 22141 93190 36225 119304 31816 46997 33449 60084 65843 24284...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 2843ms
memory: 207588kb
input:
131071 139764 478870 4 4782 1547 2947 4953 3336 3508 4282 3928 40955 209792 5 4214 616 86 4104 3099 4024 3994 1365 1027 4531 231530 91516 3 3085 3413 2092 3701 2933 4226 40015 431714 1 4764 4756 327678 328274 2 4882 3819 1767 4068 97093 266868 3 879 2008 2107 2988 4120 2907 261491 97456 2 4192 4053 ...
output:
27274 6408 588 102723 58669 20816 8478 46672 42410 73733 844 107573 39190 30387 45336 33923 41985 27314 20278 39399 46315 35755 42380 5920 113412 109707 74826 19148 18707 73650 11681 74360 66765 4404 3629 19265 14140 35353 18059 32351 696 69704 33963 1410 9113 43952 40178 6935 4132 84180 22997 24766...
result:
ok 200000 numbers
Test #18:
score: 0
Accepted
time: 2805ms
memory: 208232kb
input:
131072 6223 460632 6 2483 2393 2842 257 3518 3179 4691 3866 4420 4839 1231 2273 247781 211555 2 276 3122 4545 3262 425398 177601 4 971 679 2764 2174 1464 3566 3098 4846 232356 163195 2 4469 1931 4889 1379 386550 88052 4 3242 4291 3446 1609 4751 2330 2543 2225 452519 156503 4 3790 520 1149 647 1466 3...
output:
6208 13417 58680 29635 28147 58019 9452 11259 55255 52801 18425 23854 60997 23540 70470 72642 43355 4178 64018 35442 8237 7410 22214 40424 63910 47446 19637 53405 83758 6064 10504 26267 80024 8891 26029 19848 23749 22185 9446 97454 57990 50674 3543 9055 37796 38089 54665 14909 20941 51503 59197 9677...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 2773ms
memory: 207356kb
input:
131073 316493 134226 3 780 3985 4704 2047 416 1078 48008 126287 6 4988 1028 3318 3341 3383 4549 4241 275 3964 3949 2420 2420 335453 237601 2 1866 924 3852 35 9423 207118 5 1422 2957 1647 1127 4449 4421 2871 2912 401 538 246824 114850 2 3199 1999 2198 4479 415809 123678 3 2256 360 3457 2925 1796 1026...
output:
53510 29593 17978 8358 34248 40865 43104 90096 6781 55563 71447 6624 33577 41420 9038 103039 38104 73338 114013 53095 66427 36616 77104 46399 83191 56991 24673 19483 17851 6718 15584 7777 277 20657 13937 74652 8870 99630 24045 34743 47382 77338 55563 18271 16144 55236 12782 857 39012 17686 16225 157...
result:
ok 200000 numbers
Test #20:
score: 0
Accepted
time: 3044ms
memory: 241284kb
input:
199901 3293 2284 3 1171 2655 3120 2577 2805 4312 3025 3891 3 3723 1531 4540 4479 1421 4008 4210 1811 1 2492 2142 3204 292 4 2776 4278 695 4035 4569 1257 2269 1254 1459 81 2 3560 2675 1780 597 2988 2959 6 1392 4017 10 1770 351 1029 2078 1664 1718 4192 2599 3109 2279 155 4 3643 1851 2643 2128 3610 380...
output:
4230 137033 62455 130749 5941 16398 40711 15337 2635 7212 72282 7921 29478 2813 59569 13644 58578 6631 94895 140488 17258 37640 195731 76075 53058 114476 63415 65345 35469 86745 122531 46090 66377 57034 8757 2011 102224 71022 24914 5094 2984 146398 27257 47641 44643 114 45395 667 45343 55808 85128 7...
result:
ok 199990 numbers
Test #21:
score: 0
Accepted
time: 3049ms
memory: 241868kb
input:
200000 2543 2408 1 4912 368 1981 3459 3 910 3485 4574 2614 2736 2196 953 4370 4 1174 483 1103 515 4395 3184 4616 3927 1485 4521 3 1581 3154 3114 2121 4816 162 2234 1377 1 339 289 2921 1761 1 3350 123 848 3567 2 4505 1444 34 194 4038 23 1 543 1618 1274 3140 1 4579 4286 1805 2514 2 27 2089 1985 2267 1...
output:
55056 5065 129558 48887 7737 6893 70544 20543 20065 128053 22138 2594 63038 75004 39979 74728 94906 50369 1269 32896 59693 6927 8387 83890 63662 53547 88114 12797 49267 35553 62420 88476 43383 583 47258 24940 139951 6193 139637 142146 46322 35506 139053 41925 13909 59337 7 146270 66669 1077 4091 3 2...
result:
ok 199982 numbers
Test #22:
score: 0
Accepted
time: 3011ms
memory: 238592kb
input:
199900 78690 820471 3 4242 531 1591 1243 639 701 350077 537673 2 2906 1644 1996 2563 519283 295902 2 1692 1820 180 4879 208195 417170 1 3597 2277 282917 929980 1 798 517 615590 225385 2 4024 1291 152 4632 86541 683217 3 314 4423 2362 3917 2935 1967 33589 406147 3 4094 4478 3069 234 4285 979 454586 2...
output:
15359 114877 149266 58974 118321 40999 148940 532 14483 64287 8866 22654 129942 61632 109711 3927 153100 71435 2177 30441 28073 86539 45196 68783 82972 80262 65262 84238 117008 1087 17884 128527 48712 25016 103846 39000 61746 76189 8023 7813 10502 49894 105981 46505 9256 31425 154264 5667 45148 1006...
result:
ok 200000 numbers
Test #23:
score: 0
Accepted
time: 2991ms
memory: 237656kb
input:
199987 212495 690296 3 2211 2384 3463 1623 4397 98 788317 313858 2 1218 3653 460 2398 276899 302136 3 960 3279 3790 1492 2930 2590 592888 466734 1 1938 3102 232542 208827 3 2408 4364 153 2513 4528 3130 336342 363920 1 2451 916 553994 822203 2 505 2680 1524 2648 477482 80133 1 3366 2194 170616 431748...
output:
2848 8201 50339 6660 16767 110662 3191 24591 66905 77921 49986 30208 68132 3655 32728 38291 127466 175067 98798 14339 34081 68281 18756 2527 54881 19947 9943 22880 36424 107904 98360 37827 51983 9476 4691 47778 170101 6580 142774 86794 11847 22791 52841 54793 30466 150293 61105 16792 21133 46137 404...
result:
ok 199936 numbers
Test #24:
score: 0
Accepted
time: 2958ms
memory: 238796kb
input:
200000 607780 128071 3 4280 2827 4926 1431 1610 1681 718674 662164 4 3178 467 1478 1233 3442 3952 4196 2133 641607 7028 3 4460 3173 3768 3818 1884 232 448230 512426 4 1684 4065 1980 4706 1590 3175 2418 1606 605366 235823 3 3754 1702 4298 4142 2545 1964 692258 609171 1 189 4286 52916 189132 3 4892 84...
output:
7675 388 23524 40366 67485 3971 77425 2612 177284 73819 87300 86224 14970 18357 14912 88059 15023 97386 142963 8550 24228 39238 27597 132898 53228 65770 11733 66830 57708 97106 7567 5356 2649 28520 479 51533 125151 18769 126176 13509 50777 90839 9528 56250 159592 33753 138984 62105 69918 229 13267 6...
result:
ok 199975 numbers
Test #25:
score: 0
Accepted
time: 2312ms
memory: 228812kb
input:
199953 142561117 474175298 4 3719 154 2429 4996 2633 2432 4560 4149 141373697 22414249 3 2448 1149 4026 3041 1232 161 126914209 400530096 4 1486 3925 245 212 1811 2487 3272 1295 327219634 328108615 2 3275 757 351 627 9347529 468040920 5 1531 2208 4180 826 3699 2436 980 4886 2864 4444 62450112 451004...
output:
75447 12244 122033 124150 78605 80776 70046 46001 4905 3889 11646 12216 71533 166040 55718 142972 73624 16898 40056 12319 153304 69143 56748 47703 80338 70788 17686 60233 33504 83809 77704 4841 17081 11683 37766 51658 85399 17202 105691 48602 82006 5722 27631 87399 75189 2963 123766 2072 112062 5369...
result:
ok 199919 numbers
Test #26:
score: 0
Accepted
time: 2390ms
memory: 228452kb
input:
200000 59874959 283731044 3 638 1092 907 2892 4303 2533 223263132 50393364 1 2195 2223 95200195 145583768 3 2610 793 1421 3193 4707 639 197055310 294066377 1 741 3992 118585604 219943492 2 4815 3612 3236 1887 218563794 25623048 1 917 4569 44315832 264892800 2 2464 2670 4637 2845 97726329 154588982 1...
output:
6388 81686 31209 79809 65193 90639 3781 97032 66711 6756 22791 4381 29561 9743 17542 48047 27677 61695 12712 57494 52435 109251 85407 33906 17542 130393 33119 184388 40557 -1 90503 70517 83217 13297 9900 9027 25308 117742 69266 2966 111482 46336 147358 150891 147172 40477 110331 79050 30430 19683 87...
result:
ok 200000 numbers
Test #27:
score: 0
Accepted
time: 2340ms
memory: 229668kb
input:
200000 246174057 382791134 3 3880 3106 3734 711 4015 2302 20079721 484929831 1 2061 997 223865187 355513072 4 879 4541 3235 1301 3105 1236 1630 4533 142533043 269545254 2 4245 1903 3821 2381 393154979 154666975 4 2984 1783 1491 1837 2285 4545 374 4755 59420490 483179350 4 1994 854 457 2141 4398 336 ...
output:
27859 123483 15393 152454 47896 1201 33614 41017 185257 95292 138407 88769 112740 116135 -1 133322 65051 14877 75604 91209 58904 26078 101227 32710 2725 9863 162222 1637 68150 29277 81768 4572 60685 98204 175051 112947 69266 73996 107101 8338 5856 70244 144471 147576 59688 19088 60623 93479 3401 485...
result:
ok 199963 numbers
Test #28:
score: 0
Accepted
time: 2039ms
memory: 351236kb
input:
200000 85 80 2 883 707 58 1513 1767 0 1 3087 0 808 3948 4 192 1419 1599 27 597 1021 850 771 224 6116 4 2514 1873 2065 2312 1280 3074 4021 342 711 9955 1 111 28 229 10555 1 487 170 20 11396 4 13 1262 1079 211 774 515 256 1024 12608 311 3 1701 891 854 1750 104 2483 14710 792 2 380 9 126 266 15847 21 6...
output:
44686 8476 62791 8712 70714 -1 19902 -1 81267 161132 146323 34841 22913 29635 63141 97338 3992 16255 40877 139469 123399 174831 -1 192581 156890 41550 99146 149 116506 70649 42747 99581 10218 58946 137726 1937 7923 160633 65409 -1 93331 36229 12492 91800 142342 183775 62909 72739 163683 21518 69037 ...
result:
ok 200000 numbers
Test #29:
score: 0
Accepted
time: 3914ms
memory: 352340kb
input:
200000 18 635 1 21 474 682 465 2 907 608 1414 99 272 2386 2 910 298 167 1042 3736 129 1 298 136 148 4148 1 409 271 4960 16 1 1229 177 14 6351 2 19 1709 597 1126 7613 484 1 118 187 8192 205 2 5 957 846 119 1067 8302 1 725 153 27 10200 2 455 1078 1372 172 11741 36 1 177 37 400 11570 2 1479 142 688 943...
output:
4809 113219 19270 22649 -1 28510 46480 -1 -1 120187 5286 30255 175327 -1 35132 48373 -1 99785 22171 28 -1 -1 35212 59741 820 117119 53211 -1 -1 -1 19352 62556 26264 38722 -1 -1 151132 -1 17649 43686 52991 50944 17571 147761 72757 28818 43190 49005 -1 41258 81990 2708 163827 19888 7358 -1 46781 -1 17...
result:
ok 200000 numbers
Test #30:
score: 0
Accepted
time: 1942ms
memory: 297672kb
input:
200000 436 378 4 885 2681 306 3260 1726 1841 2404 1157 4284 99 1 447 1 436 4382 5 2405 2013 711 3674 4401 12 3522 902 3069 1358 324 8862 3 396 2333 1481 1249 2314 426 9639 2352 1 153 822 12731 186 1 289 466 11 13608 1 10 1111 14599 133 4 1479 140 622 1021 1142 488 81 1565 15202 1178 1 179 1936 16965...
output:
157518 17572 187931 199076 63066 -1 78934 60398 48066 14973 103216 56643 11650 74487 23179 82309 145622 114081 158785 40162 -1 449 122 3225 74486 185203 7394 70407 5863 89491 16328 75242 95279 82958 149790 78639 68321 -1 144343 76478 69242 62085 169527 156207 3157 87724 101731 -1 6084 82097 88390 76...
result:
ok 200000 numbers
Test #31:
score: 0
Accepted
time: 2773ms
memory: 294776kb
input:
200000 144 19 1 199 252 36 599 1 467 920 1257 749 1 11 450 2478 8 2 1372 4 872 494 3236 603 2 922 2397 3317 2 1423 5734 1 145 48 778 6561 1 408 5 3 7749 1 3 50 316 7475 1 1 69 6876 1005 1 3 798 8479 218 1 4 562 9247 8 1 5 2781 10808 1208 1 9 261 11683 604 2 1581 332 27 1877 2077 12138 1 37 102 14312...
output:
122554 166028 151591 133209 132479 83388 135665 171737 128171 64162 182032 150016 134261 119943 181370 147433 145822 88611 190288 170112 184223 148694 76436 156539 139033 119080 179451 154324 144570 132959 132450 190070 162212 129772 129764 170698 168832 79045 109670 133209 176082 134288 109820 1432...
result:
ok 200000 numbers
Test #32:
score: 0
Accepted
time: 1957ms
memory: 295992kb
input:
200000 87 517 1 2404 187 29 3068 1 207 575 3868 47 2 1099 159 280 959 4306 932 1 579 713 133 6153 3 51 2472 1644 914 2237 303 8695 319 2 1153 902 589 1446 11013 28 2 241 945 1128 47 5173 7009 3 793 914 908 794 43 1653 3693 10196 1 927 1159 14609 1387 3 1165 291 783 684 140 1319 105 17224 1 19 826 18...
output:
120717 89227 31424 138493 61473 70993 140327 32140 140750 158458 78869 3418 60211 71693 42140 16573 6841 149018 49293 74183 25820 152371 124524 38271 39644 49700 36393 58326 164776 86958 102614 164903 -1 85452 3426 -1 63791 39452 -1 185294 89165 53092 69253 63901 25820 196685 146530 21098 111233 161...
result:
ok 200000 numbers
Test #33:
score: 0
Accepted
time: 1975ms
memory: 350272kb
input:
200000 72 377 1 778 154 1358 28 1 49 1578 2270 751 2 107 465 530 46 1 3566 2 18 1196 614 605 4463 360 1 167 1561 6363 195 1 81 246 6880 6 1 1115 40 432 7542 2 2268 233 1526 970 164 10269 3 1918 1897 2983 846 163 3622 13821 551 3 1447 166 648 956 199 1399 13582 2399 1 20 771 16076 701 1 8 122 4053 12...
output:
158545 130177 64780 51445 30098 52797 -1 136448 89210 168099 -1 40962 673 89898 99618 14468 37550 18398 46467 23216 -1 150446 123787 20640 12014 22896 121336 23963 20158 182611 135346 96535 5269 -1 23636 125099 100717 62013 -1 57260 55457 -1 75367 143038 4213 47860 79442 166380 -1 33366 6156 88790 5...
result:
ok 200000 numbers
Test #34:
score: 0
Accepted
time: 3924ms
memory: 351440kb
input:
200000 13 995 1 2 208 1032 190 4 3 3241 2898 404 1961 1331 1010 2271 4474 51 4 1098 2037 69 3034 1463 1676 2152 990 7647 15 3 192 2652 1457 1394 351 2495 9960 546 2 473 1595 1207 870 12551 11 3 154 1746 1077 828 1869 29 13589 884 3 2511 230 792 1912 1485 1239 1076 15982 2 1518 596 486 1639 18848 457...
output:
438 3043 71015 29700 11928 5949 -1 50427 -1 16973 17935 1 15771 -1 3650 116535 2499 168454 154556 38442 145214 7014 32669 35009 28005 78322 772 120296 106927 150322 3176 125309 2257 -1 -1 51350 9101 26106 45192 27080 54123 126202 22634 51002 64446 7356 5630 16676 2727 36236 64183 155913 445 104033 1...
result:
ok 200000 numbers
Test #35:
score: 0
Accepted
time: 1869ms
memory: 293592kb
input:
200000 525 222 1 379 255 60 1324 1 122 227 1570 161 1 167 1047 2780 184 2 497 174 611 58 17 3593 1 956 293 606 4234 1 986 212 6001 79 1 72 113 955 5250 1 860 89 7 7098 3 1 2590 1426 1188 1035 1574 8952 872 1 2 1180 9957 1044 4 3 3713 3053 724 2139 1625 3543 239 14426 361 1 9 983 14709 1058 2 832 507...
output:
102579 99582 91117 54714 -1 30032 149771 142714 111647 187614 -1 10001 -1 34752 152947 77609 12922 114096 2743 90879 129082 21838 78367 67310 -1 -1 213 31162 194881 -1 59301 163331 622 60123 121301 91369 5185 156371 116174 79069 107588 74862 -1 33351 151658 5814 154288 -1 119127 192818 175543 -1 745...
result:
ok 200000 numbers
Test #36:
score: 0
Accepted
time: 1888ms
memory: 292964kb
input:
200000 51 343 4 4 2739 2029 746 1288 1481 444 2306 3037 44 3 1709 1327 2299 740 3 2984 6035 64 2 197 1000 48 1158 1085 6236 1 293 1207 7231 1624 2 558 72 52 568 8246 1212 3 1126 499 743 876 173 1452 10836 135 1 149 209 243 11083 2 31 495 403 107 10498 1500 6 4337 481 400 4411 1342 3491 3324 1496 214...
output:
91863 46027 -1 188189 31776 4454 13699 89554 168812 42913 42041 144291 61869 90272 129278 30969 -1 122307 33213 114115 14 128238 20117 77146 99598 166460 119332 76051 149919 64458 136537 4916 82478 128615 20724 120962 94933 14004 143755 4500 196753 76346 7926 66815 105179 -1 47879 118974 113922 1633...
result:
ok 200000 numbers
Test #37:
score: 0
Accepted
time: 2029ms
memory: 353916kb
input:
200000 1805 3 1 622 6 1294 1129 1 192 21 617 2009 1 1105 1283 3 4989 2 2241 245 3 2447 7103 433 1 10 628 8172 13 2 1526 127 7 1632 861 8873 2 1326 474 471 1315 10210 1421 1 0 1682 13151 185 3 1544 1257 2590 222 379 2408 430 15536 1 686 83 14 16700 1 4 830 17558 201 1 221 2084 20005 50 1 337 133 4279...
output:
103094 9586 134620 129734 89733 45854 -1 193681 144964 100895 44009 184001 -1 107191 71290 160114 -1 194746 114154 -1 117973 172550 70262 119612 141536 11374 175082 138964 66643 117589 91033 104013 62449 164919 58265 38067 45383 -1 80335 86258 3737 63296 86463 75431 5335 112345 15000 59405 21949 369...
result:
ok 200000 numbers
Test #38:
score: 0
Accepted
time: 3841ms
memory: 359884kb
input:
200000 646 256 4 2042 3141 486 4671 3142 2038 4813 326 146 5892 2 2686 101 347 2403 21 8752 2 103 1629 1287 438 8734 1838 5 2901 977 78 3782 3631 234 321 3547 1860 2022 6166 8311 3 3121 15 305 2865 940 2242 16982 549 2 924 210 825 307 143 18484 4 2467 443 1187 1737 1542 1380 37 2842 21510 25 2 553 4...
output:
28955 88880 73210 -1 78387 108664 -1 -1 19813 1764 56396 3863 -1 171255 36289 3 18281 19424 -1 -1 7009 52499 96956 -1 35775 25664 -1 239 -1 44800 161677 85452 27151 5378 -1 33865 63551 26170 42145 45845 178274 35779 17317 27809 10152 -1 -1 -1 17808 10893 44652 42669 85353 -1 31571 -1 108550 12210 10...
result:
ok 200000 numbers
Test #39:
score: 0
Accepted
time: 1851ms
memory: 295752kb
input:
200000 77 47 3 718 2879 2149 1436 2565 1004 282 3440 1 488 148 4273 52 2 1429 5 314 1123 197 5583 2 1987 76 1356 711 372 7471 1 758 2507 9336 1701 1 1102 582 12492 193 2 374 1567 1218 716 604 14126 2 35 1961 1736 246 16588 0 1 424 1 61 17080 2 114 1043 1099 53 2219 16094 1 235 9 3149 15413 1 32 66 9...
output:
171884 189801 30480 5344 65941 135761 76610 150752 120550 48464 167867 95427 110936 72823 47235 57070 117274 32805 74073 72823 42384 34801 42768 31485 33553 14352 140986 144232 63735 -1 124697 12028 165667 87283 7321 -1 70433 8116 17702 180252 -1 65351 169863 40832 196290 140524 181531 63837 129896 ...
result:
ok 200000 numbers
Test #40:
score: 0
Accepted
time: 2892ms
memory: 295604kb
input:
200000 6 595 3 3 3178 952 2245 2608 606 3706 110 1 1 3889 4594 3113 2 1 1842 775 1074 7371 2195 5 3285 229 286 3199 1425 2081 4 3474 2302 1210 11834 1221 1 7 1838 13963 870 2 4 1892 1632 248 16407 279 4 3 3212 658 2552 1800 1387 2619 540 11822 8179 2 952 1885 142 2717 21696 910 4 368 3744 1281 2843 ...
output:
144800 197864 127908 51986 150337 76232 79223 82713 133756 180683 106297 154050 125652 194336 159447 168815 160559 119126 119679 183257 194943 107178 159035 103404 181692 120584 159150 169589 184564 109341 196588 124718 167422 120907 77863 76039 159793 109361 121605 140792 151453 151474 197517 10642...
result:
ok 200000 numbers
Test #41:
score: 0
Accepted
time: 1874ms
memory: 294700kb
input:
200000 890 4 1 205 302 258 1248 1 29 623 2150 43 2 1748 2669 4021 384 980 5539 1 299 493 150 7182 1 135 810 8222 15 1 131 13 11 8452 1 9 413 7757 1013 1 10 992 8982 801 1 371 1660 11372 422 1 359 44 137 12074 1 87 712 12903 144 1 700 5 594 13241 1 376 198 329 14103 1 1856 391 1274 15313 1 337 1065 6...
output:
12879 92699 28205 162399 34194 42863 194377 52679 45004 56470 50838 152395 137832 111846 11931 186081 27469 -1 20506 18175 131515 24266 124206 179427 -1 141422 -1 28711 156110 24885 41168 8788 15332 81003 87535 163876 93691 14021 -1 -1 17261 142803 168460 58662 2196 18126 88135 4892 134255 39657 191...
result:
ok 200000 numbers
Test #42:
score: -100
Wrong Answer
time: 1782ms
memory: 123632kb
input:
200000 405921222 94476182 2 1185 1315 1079 1421 173441042 326953901 1 2398 102 419262353 81130113 2 126 2374 522 1978 106488017 393901962 1 2419 81 219170141 281217299 1 1415 1085 240970564 259414354 1 1274 1226 294048775 206333659 1 1536 964 355641566 144738357 1 1052 1448 161977362 338400053 1 827...
output:
5804 57317 6284 5820 87385 68621 29949 7343 66502 113154 10625 153587 4149 35638 2197 54093 28094 73482 92932 48624 52830 49965 43581 115349 3052 73536 19760 109117 94936 74184 74038 11145 138541 23075 119533 76759 35782 75931 145290 36189 7248 21608 87183 75908 38483 1041 20733 79150 103102 31662 2...
result:
wrong answer 1st numbers differ - expected: '5806', found: '5804'