QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#662285 | #7524. A Challenge For a Tourist | ucup-team3519 | AC ✓ | 432ms | 97304kb | C++17 | 5.5kb | 2024-10-20 22:34:24 | 2024-10-20 22:34:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define all0(x) (x).begin(),(x).end()
#define all1(x) (x).begin()+1,(x).end()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define cin std::cin
#define cout std::cout
typedef long long LL;
typedef pair<int, int> pi;
typedef pair<LL, LL> pl;
//const int MN = 2e5 + 20;
const int INF = 2e9 + 1000;
const LL INFLL = 8e18 + 1000;
mt19937 mrand(chrono::steady_clock().now().time_since_epoch().count());
//模板区域~~~~~~~
struct Basis{
static const int N = 30;
array<int, N> base;
int cnt = 0;
bool add(int x){
for(int i = N - 1; i >= 0; i--){
if((x >> i & 1) == 0) continue;
if(base[i]) x ^= base[i];
else {
base[i] = x;
cnt++;
return 1;
}
}
return 0;
}
int querymin(int x){
for(int i = N - 1; i >= 0; i--){
x = min(x, x ^ base[i]);
}
return x;
}
bool hav(int x) {
return querymin(x) == 0;
}
Basis operator += (Basis o) {
for(auto x : o.base) this->add(x);
return *this;
}
int size(){
return cnt;
}
};
const int N = 4e5 + 10;
namespace hdl {
V<int> e[N];
int dep[N], f[N], sz[N], hs[N], top[N];
int l[N], r[N], id[N], tot;
void dfs1(int x, int p) {
dep[x] = dep[p] + 1, f[x] = p, sz[x] = 1, hs[x] = -1;
for(auto y : e[x]) {
if(y == p) continue;
dfs1(y, x);
sz[x] += sz[y];
if(hs[x] == -1 || sz[y] > sz[hs[x]]) hs[x] = y;
}
}
void dfs2(int x, int t) {
top[x] = t, l[x] = ++tot, id[l[x]] = x;
if(hs[x] != -1) {
dfs2(hs[x], t);
}
for(auto y : e[x]) {
if(y == f[x] || y == hs[x]) continue;
dfs2(y, y);
}
r[x] = tot;
}
void build(int n){
tot = 0;
for(int i = n; i >= 1; i--) {
if(!l[i]) {
dfs1(i, 0);
dfs2(i, i);
}
}
}
int LCA(int a,int b) {
while(top[a] != top[b]) {
if(dep[top[a]] > dep[top[b]]) a = f[top[a]];
else b = f[top[b]];
}
return (dep[a] > dep[b] ? b : a);
}
}
namespace dsu {
int f[N], siz[N];
int par(int x){
if(x == f[x]) return x;
return f[x] = par(f[x]);
}
void mer(int a, int b){
a = par(a), b = par(b);
if(a == b) return;
f[a] = b;
siz[b] += siz[a];
}
void ini(int n) {
for(int i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
}
}
void solve() {
int n, m; cin >> n >> m;
V<array<int, 3>> E(m + 1);
V<int> ini_dif(m + 1);
for(int i = 1; i <= m; i++) {
auto &[x, y, z] = E[i];
cin >> x >> y >> z;
}
sort(all1(E), [&](array<int, 3> a, array<int, 3> b) {
return a[2] < b[2];
});
for(int i = 1; i <= m; i++) ini_dif[i] = E[i][2];
int q; cin >> q;
V<array<int, 3>> ask(q + 1);
V<int> ans(q + 1);
for(int i = 1; i <= q; i++) {
auto &[x, y, z] = ask[i];
cin >> x >> y >> z;
}
V<int> xordep(n + 1);
{ //cal xordep
V<int> vis(n + 1);
V<V<pi>> e(n + 1);
dsu::ini(n);
for(int i = 1; i <= m; i++) {
auto [x, y, w] = E[i];
if(dsu::par(x) == dsu::par(y)) continue;
dsu::mer(x, y);
e[x].pb({y, w}), e[y].pb({x, w});
}
auto dfs = [&](int x, int p, auto dfs) -> void {
vis[x] = 1;
for(auto [y, w] : e[x]) if(y != p) {
xordep[y] = xordep[x] ^ w;
dfs(y, x, dfs);
}
};
for(int i = 1; i <= n; i++) {
if(!vis[i]) dfs(i, 0, dfs);
}
}
for(int i = 1; i <= q; i++) {
auto &[x, y, h] = ask[i];
h ^= xordep[x] ^ xordep[y];
}
for(int i = 1; i <= m; i++) {
auto &[x, y, cyc] = E[i];
cyc ^= xordep[x] ^ xordep[y];
}
dsu::ini(n + m);
int tot = n;
V<Basis> bas(n + m + 1);
V<int> dif(n + m + 1);
for(int i = 1; i <= m; i++) {
auto [x, y, cyc] = E[i];
++tot;
int px = dsu::par(x), py = dsu::par(y);
hdl::e[tot].pb(px);
if(py != px) hdl::e[tot].pb(py);
dsu::f[px] = dsu::f[py] = tot;
bas[tot].add(cyc);
bas[tot] += bas[px];
bas[tot] += bas[py];
dif[tot] = ini_dif[i];
}
hdl::build(n + m);
dsu::ini(n + m);
for(int i = 1; i <= tot; i++) {
if(hdl::f[i] && bas[hdl::f[i]].size() == bas[i].size()) {
dsu::mer(i, hdl::f[i]);
}
}
for(int i = 1; i <= q; i++) {
auto [a, b, h] = ask[i];
int lca = hdl::LCA(a, b);
if(!lca) {
ans[i] = -1;
continue;
}
int x = lca;
while(x && !bas[x].hav(h)) x = hdl::f[dsu::par(x)];
if(x) {
// cout << "x : " << x << endl;
ans[i] = dif[x];
} else ans[i] = -1;
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
int32_t main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
solve();
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 25312kb
input:
6 6 5 6 3 6 2 2 1 2 1 2 3 2 2 4 3 4 5 4 3 1 3 1 1 3 3 1 3 5
output:
-1 2 4
result:
ok 3 number(s): "-1 2 4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 24496kb
input:
2 1 1 2 1 1 1 2 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 23728kb
input:
5 10 1 2 4 2 2 0 1 1 7 2 1 7 4 1 1 5 5 1 4 1 4 5 2 6 1 1 2 2 4 7 10 1 4 3 1 2 5 3 2 1 3 5 5 2 4 0 3 2 0 2 1 2 2 3 6 5 1 7 2 3 3
output:
2 6 -1 -1 4 -1 6 -1 6 -1
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 22640kb
input:
10 20 3 5 667 2 5 71 2 9 47 7 9 941 9 1 564 2 1 892 7 1 627 2 2 989 8 9 978 1 3 936 1 1 807 8 4 564 6 9 518 5 4 896 2 9 607 3 9 453 1 3 402 10 8 935 7 3 826 1 6 707 40 3 10 164 2 10 248 5 6 708 5 9 764 1 9 711 3 8 377 9 1 640 7 1 554 3 1 504 4 9 761 1 8 111 5 8 296 4 2 97 10 4 896 5 1 232 5 8 154 7 ...
output:
-1 941 -1 -1 -1 941 941 936 892 -1 896 -1 896 -1 -1 896 -1 941 -1 936 936 936 941 941 892 -1 -1 941 826 -1 896 -1 -1 936 896 -1 941 941 941 941
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 22612kb
input:
20 40 11 3 622 15 1 463 1 13 754 10 16 87 17 16 602 19 4 1003 4 5 50 1 12 598 13 11 600 8 12 26 8 3 325 18 17 329 9 15 961 12 6 110 8 12 756 8 6 415 19 11 159 8 6 595 6 6 32 10 15 573 18 9 659 2 16 685 11 15 881 10 11 614 20 8 941 12 17 473 12 20 796 17 12 881 13 4 870 5 1 76 19 3 191 17 8 698 7 20 ...
output:
685 796 685 659 614 622 796 685 615 685 622 -1 -1 622 622 622 622 796 685 614 622 622 796 602 685 615 615 796 -1 622 796 685 659 614 685 659 614 685 685 685 685 659 -1 685 685 685 685 796 685 685 -1 685 598 796 685 796 796 622 -1 685 685 622 685 622 622 615 622 685 -1 -1 -1 685 796 615 615 796 685 7...
result:
ok 80 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 22636kb
input:
30 60 20 6 610 28 8 847 1 9 442 30 5 574 5 23 49 12 17 415 3 24 116 3 22 164 3 16 464 27 1 179 19 11 689 16 8 840 12 28 242 13 14 300 20 21 243 6 7 50 10 28 207 27 2 858 5 17 164 27 19 839 28 25 399 10 11 185 6 10 157 24 8 309 2 22 722 5 4 688 13 19 314 10 15 858 13 22 286 12 24 376 29 17 37 7 4 762...
output:
526 513 513 513 464 526 442 513 526 513 526 526 526 526 513 376 513 526 526 526 513 513 526 513 498 526 464 526 498 394 526 526 526 526 526 526 498 526 526 526 526 526 526 526 442 498 526 513 526 526 513 526 513 526 513 526 513 513 513 376 526 442 513 513 513 415 464 415 498 513 526 498 498 464 513 ...
result:
ok 120 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 22608kb
input:
40 80 12 19 34 3 23 7 2 6 779 20 14 464 14 38 950 39 1 46 14 13 18 17 16 736 4 35 816 9 13 507 27 38 18 1 3 905 29 9 628 3 32 740 37 3 410 23 33 428 19 8 69 38 34 501 35 31 446 9 7 831 34 21 33 14 7 133 9 24 545 18 9 247 20 6 10 19 24 176 4 30 780 14 15 108 1 10 263 17 38 748 38 2 894 36 28 556 2 7 ...
output:
556 545 412 -1 -1 464 545 556 464 545 464 556 -1 295 545 424 556 545 545 365 464 545 556 556 412 556 412 464 464 556 545 464 545 464 -1 556 556 464 464 424 -1 410 -1 -1 -1 556 545 295 464 545 556 412 464 545 464 545 -1 545 -1 295 545 545 464 545 -1 545 -1 556 558 410 -1 464 545 464 464 -1 -1 424 -1 ...
result:
ok 160 numbers
Test #8:
score: 0
Accepted
time: 5ms
memory: 23640kb
input:
50 100 33 19 845 50 31 685 27 25 461 15 36 18 17 35 853 49 32 539 7 6 840 24 8 1013 26 31 438 25 29 943 7 17 547 9 4 976 43 50 94 10 23 938 46 47 649 13 6 894 42 20 854 16 27 51 17 4 690 6 18 456 37 8 44 12 35 681 18 43 306 47 24 882 38 46 91 27 29 998 13 22 894 31 18 1010 42 27 165 9 2 75 6 19 588 ...
output:
512 674 -1 701 544 541 572 572 572 674 572 572 541 572 544 544 544 588 853 572 572 572 572 572 572 539 572 572 572 544 -1 572 541 572 544 572 572 541 572 674 544 588 588 544 588 544 572 853 572 507 572 674 714 674 572 714 853 732 572 732 572 512 588 541 544 572 544 714 572 572 -1 853 541 544 541 572...
result:
ok 200 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 25420kb
input:
60 120 34 41 6 4 31 444 54 5 918 58 8 474 6 44 453 43 52 497 43 59 354 25 40 189 26 23 273 19 42 977 6 1 296 55 56 716 22 21 116 22 46 392 52 7 103 10 26 502 60 39 358 14 20 646 48 4 772 17 29 759 11 40 781 3 8 637 21 46 886 28 21 181 7 48 425 36 40 2 43 33 803 59 21 859 36 28 548 4 9 951 57 13 170 ...
output:
525 611 386 -1 524 679 562 474 611 525 386 525 -1 951 735 386 611 358 591 386 425 340 764 524 524 918 591 386 525 764 524 524 525 524 524 525 611 951 524 524 524 951 524 735 386 918 591 951 525 386 524 525 -1 348 764 524 951 524 524 524 -1 764 386 525 759 340 951 679 759 951 386 524 524 716 358 524 ...
result:
ok 240 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 25052kb
input:
70 140 14 56 377 66 1 557 34 54 500 21 55 342 70 3 452 21 16 1004 37 59 623 54 39 1001 32 32 964 63 59 208 57 7 785 46 24 324 23 39 724 9 54 482 21 21 734 54 46 197 19 56 222 63 45 731 6 18 56 7 33 582 10 68 40 29 18 276 3 32 651 25 43 920 47 6 404 39 62 946 56 49 839 35 57 168 2 49 367 12 6 442 42 ...
output:
594 539 539 539 635 450 539 472 490 539 525 594 539 539 543 539 539 920 539 696 582 472 472 539 450 594 539 573 543 573 649 472 594 490 573 539 539 464 543 450 519 472 635 539 453 539 472 519 472 543 525 539 450 644 644 482 696 594 635 444 539 644 539 543 412 920 594 519 453 539 594 490 519 450 539 ...
result:
ok 280 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 23956kb
input:
80 160 29 67 324 31 48 232 75 20 778 18 21 597 49 39 197 42 77 854 29 70 689 45 22 63 10 4 782 27 28 141 5 71 626 23 9 151 37 62 844 63 19 984 44 80 982 68 9 99 75 62 138 41 32 230 20 13 611 35 71 916 47 26 436 45 73 748 30 75 64 29 9 861 17 8 840 59 73 230 17 6 204 75 59 608 47 41 444 43 79 703 63 ...
output:
844 515 664 603 448 664 953 515 515 626 515 515 603 953 515 844 515 515 508 935 459 635 515 448 736 -1 515 576 448 844 515 878 515 576 576 -1 576 664 501 459 501 515 515 664 626 736 515 515 501 953 501 501 515 703 635 523 635 515 664 501 459 626 576 703 935 878 603 635 844 515 515 501 783 454 523 50...
result:
ok 320 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 25044kb
input:
90 180 82 2 648 85 65 932 10 78 136 48 6 670 69 21 697 55 50 763 71 60 455 62 20 665 74 12 173 89 27 750 19 38 83 47 24 152 66 73 370 84 22 941 6 12 571 74 37 568 20 37 954 5 74 998 86 48 986 29 64 32 53 57 693 9 73 69 39 49 765 32 45 997 49 50 543 51 46 790 65 87 255 50 65 480 23 87 732 27 35 220 1...
output:
699 514 568 514 514 720 568 648 648 665 699 480 665 528 528 464 514 948 699 461 699 514 720 528 600 871 528 600 699 571 611 514 790 871 528 665 514 1021 720 492 790 699 720 480 699 597 528 665 528 699 528 568 514 528 699 1021 571 699 699 568 699 514 568 568 599 492 790 528 528 528 699 568 720 514 61...
result:
ok 360 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 23688kb
input:
100 200 6 45 162 46 33 419 18 88 669 75 4 966 64 3 262 66 35 479 30 76 952 20 80 734 28 48 51 28 64 307 46 24 566 23 89 429 14 66 609 73 15 344 81 82 880 100 67 724 60 14 596 98 17 417 32 24 731 72 12 163 70 66 216 8 7 852 43 16 776 100 75 760 39 18 726 6 66 278 45 71 691 84 58 1011 58 88 892 28 71 ...
output:
528 514 720 609 581 429 468 514 528 528 528 429 528 552 528 479 514 691 514 517 585 514 585 806 585 528 585 434 528 514 528 514 528 720 552 552 609 528 514 528 528 479 528 517 344 514 417 528 609 528 446 806 806 528 528 -1 550 434 806 691 550 528 806 609 528 479 552 514 552 528 806 514 514 -1 514 60...
result:
ok 400 numbers
Test #14:
score: 0
Accepted
time: 417ms
memory: 97108kb
input:
200000 200000 109342 177585 227729360 47204 185227 65000004 18413 107067 731586911 193618 193271 176899956 193975 45521 123073233 21309 181614 329804012 138160 118319 203452859 124884 8693 566070106 159912 46179 902860088 166651 68050 474901516 186453 75667 211242475 128492 19333 1063841125 15161 12...
output:
-1 -1 867002222 756893127 893777656 794446704 1047710880 928938116 665867444 756355523 619390985 -1 921982297 -1 -1 -1 -1 984785973 693903984 683706666 845743685 -1 646184093 934291503 873911518 616673597 830156759 -1 676344238 818209218 -1 959609719 -1 830776927 720735705 -1 969168009 829364544 -1 ...
result:
ok 200000 numbers
Test #15:
score: 0
Accepted
time: 413ms
memory: 97228kb
input:
200000 200000 87 159493 1004393170 21352 10917 196334107 58787 62730 943561852 29814 80998 892175899 106351 98220 532814271 179725 112396 746992581 188089 8377 685730287 73722 68193 194367885 192153 5848 706209688 36993 27859 427824942 165200 100710 810280288 45066 141749 232346113 92544 77436 74624...
output:
-1 725561349 -1 -1 1041814832 -1 566535611 -1 847790168 -1 801117050 767199268 -1 897632551 -1 694156002 1028718162 851852574 778415440 837247383 -1 925715962 -1 617554679 947622426 797075601 732345765 581795607 581395898 -1 1054670730 714012171 927590703 843385218 -1 594420845 811897992 705988900 7...
result:
ok 200000 numbers
Test #16:
score: 0
Accepted
time: 412ms
memory: 97304kb
input:
200000 200000 198494 165643 575324511 181016 66449 1065322153 165181 143397 24581834 143391 198983 9866629 179665 194682 497649408 90640 194984 613451737 167407 18673 628528759 199136 142368 576713736 171940 179822 826229364 105815 77923 304986038 54646 16951 161446326 72319 20628 692179685 24524 13...
output:
1034511907 857626129 -1 -1 630373350 878226623 -1 770204552 -1 -1 750734050 -1 680993075 -1 937880944 622514993 -1 -1 -1 629784547 862196200 -1 666733467 715120680 980307839 718824125 622193052 802260393 794996087 654935584 952736251 710294889 997845249 -1 743687945 -1 1044320027 574705974 -1 -1 624...
result:
ok 200000 numbers
Test #17:
score: 0
Accepted
time: 417ms
memory: 97144kb
input:
200000 200000 181419 149800 722194190 184899 30233 406526416 12627 184368 461819352 50406 184138 56072711 36649 146020 11103399 58305 63525 1054497174 65445 111320 294974203 28050 122695 823135923 13527 81202 641920496 117506 29016 68060418 135134 92575 582554935 82301 181136 404220218 106083 119484...
output:
569288751 831434641 -1 920862069 979288812 747342841 647773540 698123047 -1 943985851 683746818 -1 620927288 659909725 661858842 -1 683959261 -1 -1 -1 730409534 -1 871186574 -1 598350740 -1 -1 1010240795 933657223 745412390 905357550 871574299 648279218 -1 742171929 -1 -1 -1 594628096 -1 613752538 6...
result:
ok 200000 numbers
Test #18:
score: 0
Accepted
time: 432ms
memory: 97180kb
input:
200000 200000 44161 78677 608279087 88995 53260 981544094 146705 177900 534397056 21607 144362 39446700 155677 104939 773366612 60554 3880 936090968 10726 134856 868155296 81383 129346 677461739 10580 137609 748717579 89496 66945 47831733 13395 163913 1022791866 921 66884 729817045 183045 3368 29298...
output:
-1 584622481 820541910 -1 854155129 790994153 999729010 654981781 940073167 903255303 995576344 -1 -1 678814274 -1 1026097915 -1 -1 655155315 709024139 630356732 921141385 -1 641608685 763652771 -1 738774378 747978959 -1 -1 694241664 663894145 -1 814509249 960285895 1029364395 807730051 -1 705849960...
result:
ok 200000 numbers
Test #19:
score: 0
Accepted
time: 421ms
memory: 97112kb
input:
200000 200000 50621 23085 799318104 169569 2113 488786657 56313 136715 144934133 19820 34052 763518186 116851 157271 258218883 18302 196537 1034089281 144015 109808 333489262 30315 62782 611603377 135977 52103 767929284 28680 172928 78682125 134933 74616 770607930 71492 187418 287070180 159778 83817...
output:
-1 -1 -1 812630173 -1 847390275 -1 949031773 1064718647 -1 -1 689565788 837528029 622816397 974081560 887226865 -1 751230044 957884451 -1 -1 887281377 702502518 679545644 626540089 594378110 635582388 742932582 571842692 1023438234 762729206 898407139 -1 792391889 -1 -1 861339430 -1 -1 696630325 759...
result:
ok 200000 numbers
Test #20:
score: 0
Accepted
time: 411ms
memory: 77556kb
input:
100000 200000 41586 4424 697628463 81874 32727 208545646 26932 64908 1047751949 9726 59915 296089205 55006 21898 526800356 34083 66394 241951281 87192 40916 894678925 9183 84409 293533088 3387 83932 275770761 66353 38672 521187462 11306 52107 195091056 30776 66998 951473510 17009 10252 373626096 169...
output:
706479056 796570207 445303222 710407692 833479688 662355681 15569184 345554721 908977568 45999363 463292219 309520961 857093307 1073710164 864568445 517049595 826679496 811154941 266781591 962897393 643219087 796800215 776180302 680232756 501930828 976337957 867145367 857945302 1073683682 893884404 ...
result:
ok 200000 numbers
Test #21:
score: 0
Accepted
time: 303ms
memory: 76324kb
input:
110000 187585 23693 23693 260328316 40017 40017 717849382 76058 76058 345207845 5941 5941 973620527 74929 52756 132156947 46284 46284 110519088 52066 52066 318618469 83388 41304 575280127 4148 4148 308823289 31813 31813 819265914 52574 52574 464610702 85712 85712 594912755 57980 57980 715289602 4846...
output:
-1 -1 -1 -1 -1 -1 -1 -1 982852221 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 784874877 -1 -1 622037727 829448916 -1 -1 971099102 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 676741976 -1 -1 84122119 -1 258524673 851307700 -1 -1 -1 227041043 -1 -1 -1 6466066 -1 -1 -1 -1 606413750 -1 -1 -1 -1 -1 -1 ...
result:
ok 187585 numbers
Test #22:
score: 0
Accepted
time: 249ms
memory: 71592kb
input:
120000 157963 13010 13010 591417088 9861 9861 620650301 93208 93208 37890427 107309 107309 856767877 4841 4841 787590669 77765 77765 63516790 82372 82372 331101147 92362 92362 587628783 49180 49180 481813350 109909 109909 236720887 35959 35959 759588545 27704 27704 611701950 96701 96701 769172731 72...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 750010032 -1 -1 324111713 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1006614616 -1 -1 641263513 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 926915009 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 157963 numbers
Test #23:
score: 0
Accepted
time: 360ms
memory: 80316kb
input:
130000 192084 86538 86538 874548688 33144 62295 775596530 17017 17017 244289422 3693 4593 758037079 102443 40730 499644950 21496 21496 395379125 92791 103683 916000668 13765 13765 640962394 41498 2592 162403493 123890 99930 197456048 48793 71546 902353306 22206 22206 452920051 114921 24437 150946796...
output:
702395897 72145842 99604830 -1 -1 427210678 407030613 260253724 1045545089 560488259 513877080 -1 614376204 625375721 -1 81813949 -1 1027121529 -1 431253808 866161920 -1 210183864 977103891 274754544 154995486 473187706 -1 386545407 219713047 655374672 392027077 703895480 149080597 700000200 2283593...
result:
ok 192084 numbers
Test #24:
score: 0
Accepted
time: 323ms
memory: 78580kb
input:
140000 176204 65376 65376 1028064266 19771 90515 878833054 105136 76429 135953113 75169 69211 376168990 65718 114589 323501713 29108 31149 948963783 53348 53348 93371590 12292 89441 1013528906 31988 28892 948262432 122679 53720 654657391 79137 79137 327732460 27150 77535 7479827 117090 117090 590992...
output:
-1 91695842 -1 1072645411 -1 989243311 528596959 548338498 -1 428937247 124931964 -1 -1 -1 261732347 -1 -1 861544067 -1 -1 -1 408611658 15637088 897780261 826187544 627399306 684388859 -1 665737530 438039641 352216189 245567184 -1 535538282 -1 -1 -1 673898224 -1 829234398 895582909 -1 959535788 1027...
result:
ok 176204 numbers
Test #25:
score: 0
Accepted
time: 314ms
memory: 83288kb
input:
150000 191723 60958 48382 506073494 115490 115490 613984068 6445 6445 904345931 116322 116322 473345203 93164 93164 225385764 78513 83320 214801600 105818 105818 797637676 54442 147123 87337901 130241 130241 220314537 33845 5571 367406727 102082 59953 730208587 145584 145584 351343892 54077 54077 32...
output:
-1 -1 -1 378448195 -1 566535791 852978490 -1 -1 1019622166 -1 679204997 -1 -1 -1 913831333 -1 -1 -1 182487140 -1 -1 465537899 614623361 704640058 -1 -1 -1 -1 570562033 176037425 673115932 -1 84052876 -1 -1 710474201 -1 100852295 -1 -1 670183326 196374133 982511418 -1 -1 -1 335001712 -1 -1 -1 5895680...
result:
ok 191723 numbers
Test #26:
score: 0
Accepted
time: 354ms
memory: 80652kb
input:
160000 175843 149258 91345 121217762 141545 15575 313462396 150778 108103 513023667 87461 100025 1043452531 11145 151603 681276991 6303 24370 733293126 33000 33000 5667183 11935 6640 794238421 81626 40228 809250484 65922 65922 464064029 83523 87801 701438153 48106 30039 107190454 7149 9327 929964961...
output:
546649649 797518618 872460490 413930609 854773235 119648686 782069118 132268245 272055226 977483671 703718991 289155075 930718536 -1 457179186 437412118 519172401 256813169 100664549 766809922 389579432 986988061 665112035 845436100 -1 595658993 245637618 822735806 1035906276 774746740 54900390 5214...
result:
ok 175843 numbers
Test #27:
score: 0
Accepted
time: 321ms
memory: 80060kb
input:
170000 159964 73910 81276 90183505 107899 19484 210894288 133053 133053 699350234 105418 124580 576665443 52835 157518 359041865 104062 127961 749172598 96869 7390 377479836 163888 88656 926913391 69524 27918 337717645 105914 146164 766978916 53592 24169 558867234 8203 149774 164508526 50840 78409 2...
output:
571486043 -1 546680631 760191679 386679482 957001255 260751507 42709042 405288183 255874392 685971806 353975615 212064408 -1 882764013 870898775 867332084 936818351 342204532 -1 728573419 124552759 420389295 764553776 440417549 129677110 521676120 1011105275 -1 313394926 59967058 655641434 -1 922994...
result:
ok 159964 numbers
Test #28:
score: 0
Accepted
time: 333ms
memory: 87756kb
input:
180000 194085 11114 11114 827265831 164474 111250 718600578 111685 111685 94367111 163799 163799 842132447 137765 137765 1001023618 119023 119023 107931024 40872 40872 201676153 140651 5369 8499149 77483 77483 307058366 158825 158825 200100346 134564 134564 175636512 148209 148209 1044942754 171406 ...
output:
-1 156118328 -1 -1 365953067 -1 -1 329688466 -1 -1 604835796 1022163491 -1 221539042 393702501 -1 -1 -1 -1 712981227 526818792 1041823763 -1 -1 -1 -1 32141994 329649937 -1 545206010 -1 638328158 821984824 -1 39908755 -1 153254669 -1 -1 -1 -1 -1 -1 -1 968179320 88320478 -1 -1 -1 -1 -1 -1 580053395 -1...
result:
ok 194085 numbers
Test #29:
score: 0
Accepted
time: 300ms
memory: 82672kb
input:
190000 164463 62571 34777 896876064 111874 111874 438003059 150172 148535 738069714 2089 100134 595189640 128538 163263 1007449887 142611 126848 706959845 45428 45428 774310434 40107 40107 850208491 16794 63343 1072548477 58851 128239 172831056 94685 186673 954255784 13928 93485 339338714 37874 3787...
output:
557476195 -1 672943255 -1 374624679 289986746 -1 879915378 -1 -1 979151772 442009803 -1 681347100 657041740 -1 -1 -1 679691230 550720428 -1 879472003 -1 999209688 167999132 -1 1039665392 -1 -1 -1 494272760 292426391 -1 291318574 844385108 305602217 839672990 512150752 -1 -1 -1 418777187 -1 -1 -1 -1 ...
result:
ok 164463 numbers
Test #30:
score: 0
Accepted
time: 344ms
memory: 84660kb
input:
200000 164443 86136 58617 423675455 4590 45193 325177905 129516 35839 446384631 180314 180314 540065528 167297 123694 68290106 134121 174065 796223221 127351 59018 612051986 62959 123335 351293941 50045 15133 592116369 163872 172640 958111857 33009 165864 106055980 74104 154008 159958151 142980 7522...
output:
-1 626760387 -1 806728558 16613352 891755096 674521156 403857182 571227425 492029315 864532640 5370067 295375690 38664282 776407076 146711939 909718418 520450081 675229288 798697856 369171310 387673047 380187900 502525484 268269150 891847813 820373637 873643252 686027135 631187506 571582402 57025905...
result:
ok 164443 numbers