QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#530898#5706. Villageisirazeev50 277ms21996kbC++203.6kb2024-08-24 17:35:092024-08-24 17:35:14

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 17:35:14]
  • 评测
  • 测评结果：50
  • 用时：277ms
  • 内存：21996kb
查看
  • [2024-08-24 17:35:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 10;

vector<int> g[N];
int sz[N], used[N];

inline void sizes(int v, int p = -1) {
    sz[v] = 1;
    for (auto u: g[v]) {
        if (u != p && !used[u])
            sizes(u, v), sz[v] += sz[u];
    }
}

inline int centroid(int v, int p, int Size) {
    for (auto u: g[v]) {
        if (u != p && !used[u] && sz[u] > Size / 2)
            return centroid(u, v, Size);
    }
    return v;
}

int n, pr[N], from[N];
long long res = 0;

vector<int> vertex;

inline void dfs(int v, int p) {
    vertex.emplace_back(v);
    for (auto u: g[v]) {
        if (u != p && !used[u])
            dfs(u, v);
    }
}

inline void solve(int v) {
    sizes(v);
    int C = centroid(v, -1, sz[v]);
    sizes(C);
    used[C] = true;
    vector<vector<int>> node;
    for (auto u: g[C]) {
        if (!used[u]) {
            vertex.clear();
            dfs(u, -1);
            node.emplace_back(vertex);
        }
    }
    if (!node.empty()) {
        vector<int> ord((int) node.size());
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
            return node[i].size() < node[j].size();
        });
        if (sz[C] % 2 == 0) node[ord[0]].emplace_back(C);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
            return node[i].size() < node[j].size();
        });
        vector<vector<int>> copy = node;
        for (int i = 0; i < (int) node.size(); i++) node[i] = copy[ord[i]];
        copy = node;
        reverse(copy.begin(), copy.end());
        for (int i = 0; i < (int) node.size() - 1; i++) {
            int j = i + 1;
            while (!node[i].empty()) {
                pr[from[node[i].back()]] = node[j].back();
                pr[from[node[j].back()]] = node[i].back();
                int t1 = from[node[i].back()], t2 = from[node[j].back()];
                from[node[i].back()] = t2, from[node[j].back()] = t1;
                node[i].pop_back(), node[j].pop_back();
            }
        }
        int i = (int) node.size() - 1;
        while (!node.back().empty()) {
            while (!copy.empty() && copy.back().empty()) copy.pop_back();
            pr[from[node[i].back()]] = copy.back().back();
            pr[from[copy.back().back()]] = node[i].back();
            int t1 = from[node[i].back()], t2 = from[copy.back().back()];
            from[node[i].back()] = t2, from[copy.back().back()] = t1;
            node[i].pop_back(), copy.back().pop_back();
        }
    }
    int son = -1;
    for (auto u: g[C]) {
        if (!used[u])
            solve(u), son = u;
    }
    if (pr[C] == C) {
        int new_son = pr[from[son]];
        pr[from[son]] = C, pr[from[C]] = new_son;
        int t1 = from[son], t2 = from[C];
        from[C] = t1, from[new_son] = t2;
    }
}

void gfs(int v, int p) {
    sz[v] = 1;
    for (auto u: g[v]) {
        if (u != p) {
            gfs(u, v), sz[v] += sz[u];
            res += min(n - sz[u], sz[u]);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u - 1].emplace_back(v - 1);
        g[v - 1].emplace_back(u - 1);
    }
    for (int i = 0; i < n; i++) pr[i] = from[i] = i;
    gfs(0, -1);
    solve(0);
    cout << res * 2 << " " << res * 2 << '\n';
    for (int i = 0; i < n; i++)
        cout << pr[i] + 1 << " ";
    cout << '\n';
    for (int i = 0; i < n; i++)
        cout << pr[i] + 1 << " ";
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 6
Acceptable Answer

Test #1:

score: 6
Acceptable Answer
time: 1ms
memory: 3528kb

input:

4
1 2
2 3
3 4

output:

8 8
3 4 1 2 
3 4 1 2

result:

points 0.50 jury has the better answer; correct answer = 8;

Test #2:

score: 6
Acceptable Answer
time: 1ms
memory: 3616kb

input:

7
4 2
5 7
3 4
6 3
1 3
4 5

output:

18 18
4 3 7 5 6 2 1 
4 3 7 5 6 2 1

result:

points 0.50 jury has the better answer; correct answer = 18;

Test #3:

score: 12
Accepted
time: 1ms
memory: 3764kb

input:

2
1 2

output:

2 2
2 1 
2 1

result:

points 1.0 correct answer = 2; correct answer = 2;

Test #4:

score: 6
Acceptable Answer
time: 1ms
memory: 3816kb

input:

7
4 1
7 6
7 5
1 3
3 2
1 6

output:

20 20
6 7 1 5 3 2 4 
6 7 1 5 3 2 4

result:

points 0.50 jury has the better answer; correct answer = 20;

Test #5:

score: 6
Acceptable Answer
time: 1ms
memory: 3820kb

input:

7
2 7
5 2
6 1
1 4
4 5
7 3

output:

24 24
7 6 5 3 4 2 1 
7 6 5 3 4 2 1

result:

points 0.50 jury has the better answer; correct answer = 24;

Test #6:

score: 6
Acceptable Answer
time: 1ms
memory: 3624kb

input:

7
5 3
3 6
3 1
1 7
1 4
5 2

output:

18 18
2 4 1 5 7 3 6 
2 4 1 5 7 3 6

result:

points 0.50 jury has the better answer; correct answer = 18;

Test #7:

score: 12
Accepted
time: 1ms
memory: 3640kb

input:

7
7 3
4 7
1 7
7 2
5 7
7 6

output:

12 12
2 1 4 3 7 5 6 
2 1 4 3 7 5 6

result:

points 1.0 correct answer = 12; correct answer = 12;

Test #8:

score: 6
Acceptable Answer
time: 1ms
memory: 3648kb

input:

8
4 8
5 2
6 2
3 8
4 7
2 8
2 1

output:

22 22
3 4 2 6 8 7 5 1 
3 4 2 6 8 7 5 1

result:

points 0.50 jury has the better answer; correct answer = 22;

Test #9:

score: 6
Acceptable Answer
time: 1ms
memory: 5852kb

input:

9
8 1
3 5
8 3
6 8
7 8
3 9
8 4
2 3

output:

22 22
5 1 8 2 7 3 9 4 6 
5 1 8 2 7 3 9 4 6

result:

points 0.50 jury has the better answer; correct answer = 22;

Test #10:

score: 6
Acceptable Answer
time: 1ms
memory: 3640kb

input:

10
9 8
1 3
7 5
8 6
8 10
6 4
1 6
10 2
6 5

output:

30 30
2 7 10 1 9 3 8 4 6 5 
2 7 10 1 9 3 8 4 6 5

result:

points 0.50 jury has the better answer; correct answer = 30;

Test #11:

score: 6
Acceptable Answer
time: 1ms
memory: 5680kb

input:

10
9 2
10 4
10 5
2 5
8 3
3 6
7 4
9 8
1 6

output:

50 50
5 6 4 3 1 10 9 7 2 8 
5 6 4 3 1 10 9 7 2 8

result:

points 0.50 jury has the better answer; correct answer = 50;

Test #12:

score: 6
Acceptable Answer
time: 1ms
memory: 3816kb

input:

10
5 7
4 1
10 5
9 3
7 9
8 2
6 1
8 6
2 7

output:

42 42
3 10 2 5 4 9 1 7 6 8 
3 10 2 5 4 9 1 7 6 8

result:

points 0.50 jury has the better answer; correct answer = 42;

Test #13:

score: 6
Acceptable Answer
time: 1ms
memory: 5908kb

input:

10
6 10
2 7
10 1
10 8
4 2
1 5
1 9
2 3
10 2

output:

28 28
7 10 9 1 2 5 8 4 6 3 
7 10 9 1 2 5 8 4 6 3

result:

points 0.50 jury has the better answer; correct answer = 28;

Test #14:

score: 12
Accepted
time: 1ms
memory: 3588kb

input:

10
5 6
3 5
8 5
5 7
5 1
2 5
9 5
5 4
5 10

output:

18 18
7 9 6 10 3 8 1 5 2 4 
7 9 6 10 3 8 1 5 2 4

result:

points 1.0 correct answer = 18; correct answer = 18;

Test #15:

score: 6
Acceptable Answer
time: 0ms
memory: 3620kb

input:

10
4 1
5 4
5 10
6 1
8 5
9 4
3 1
7 4
1 2

output:

28 28
4 8 5 2 6 7 3 9 10 1 
4 8 5 2 6 7 3 9 10 1

result:

points 0.50 jury has the better answer; correct answer = 28;

Test #16:

score: 6
Acceptable Answer
time: 1ms
memory: 3580kb

input:

10
10 2
4 10
1 10
5 10
10 7
9 10
3 10
1 6
8 1

output:

22 22
5 6 10 1 8 4 9 2 7 3 
5 6 10 1 8 4 9 2 7 3

result:

points 0.50 jury has the better answer; correct answer = 22;

Test #17:

score: 6
Acceptable Answer
time: 1ms
memory: 5924kb

input:

10
5 9
8 1
6 2
4 3
6 7
1 5
3 10
6 8
3 1

output:

34 34
6 9 7 8 3 5 1 4 10 2 
6 9 7 8 3 5 1 4 10 2

result:

points 0.50 jury has the better answer; correct answer = 34;

Subtask #2:

score: 19
Acceptable Answer

Dependency #1:

50%
Acceptable Answer

Test #18:

score: 19
Acceptable Answer
time: 1ms
memory: 5716kb

input:

256
229 81
255 131
55 23
79 6
37 152
3 58
173 242
17 131
116 72
109 201
92 187
215 83
101 253
224 23
101 157
219 236
214 61
41 78
190 232
184 215
39 145
215 94
21 255
59 178
255 215
25 63
46 41
77 203
164 206
28 147
195 134
204 155
215 256
107 167
202 95
206 69
57 222
87 25
52 63
69 234
73 110
54 34...

output:

2186 2186
24 253 93 35 239 124 100 162 61 158 232 235 171 193 166 30 222 28 18 8 7 227 47 228 116 94 241 160 217 150 229 236 118 132 230 159 207 71 29 204 36 255 59 153 46 91 81 172 2 252 109 248 101 114 194 9 127 208 64 189 108 89 72 146 187 53 225 6 188 234 70 107 11 41 215 12 141 102 34 137 213 1...

result:

points 0.50 jury has the better answer; correct answer = 2186;

Test #19:

score: 19
Acceptable Answer
time: 0ms
memory: 3872kb

input:

500
223 499
155 198
156 203
423 438
87 11
3 73
394 298
59 42
394 147
499 377
50 44
144 298
131 147
10 38
235 430
463 288
103 165
339 354
467 76
414 450
50 206
129 443
147 409
476 409
445 239
111 398
293 273
349 296
131 149
206 92
454 183
313 209
390 480
155 406
494 75
408 382
10 100
166 102
123 332
...

output:

5114 5114
205 26 275 122 163 269 277 23 66 339 98 119 107 6 337 434 68 458 388 131 240 406 435 11 392 378 130 247 83 426 70 439 293 462 193 475 84 354 184 126 431 33 143 368 67 256 454 243 139 223 440 246 47 308 414 334 164 357 370 39 222 25 375 76 490 141 262 86 235 305 341 19 137 215 372 296 268 3...

result:

points 0.50 jury has the better answer; correct answer = 5114;

Test #20:

score: 19
Acceptable Answer
time: 1ms
memory: 3736kb

input:

499
239 23
393 140
346 79
261 477
343 157
9 31
466 9
459 488
365 191
38 405
302 340
413 434
227 499
40 318
289 373
290 394
21 479
287 322
52 378
422 283
86 369
39 444
19 321
132 302
31 364
301 142
417 6
25 219
199 223
405 372
133 67
89 449
412 39
382 418
21 379
244 391
477 469
246 484
423 416
6 9
36...

output:

4106 4106
386 143 88 373 226 42 50 492 14 73 264 148 43 242 209 335 121 298 413 462 291 231 277 466 116 384 39 53 443 125 408 34 12 216 347 498 278 375 74 111 325 290 184 29 468 343 173 215 404 41 279 445 101 13 189 333 282 255 257 287 455 370 399 20 203 164 314 67 382 85 318 222 165 444 9 237 499 3...

result:

points 0.50 jury has the better answer; correct answer = 4106;

Test #21:

score: 19
Acceptable Answer
time: 1ms
memory: 3704kb

input:

1000
842 343
479 865
720 325
420 693
317 105
694 123
626 422
306 24
186 483
37 830
103 33
328 345
379 819
79 946
835 433
939 455
271 587
980 524
316 643
204 621
573 60
935 924
984 435
880 123
626 3
689 794
110 378
827 351
487 932
201 193
836 706
874 293
889 845
179 815
800 267
43 934
954 916
805 548...

output:

14376 14376
677 907 545 958 633 68 643 457 647 685 587 62 955 332 156 246 723 817 65 371 870 109 601 855 654 634 690 830 903 515 359 126 750 520 158 932 473 452 276 248 911 238 710 272 242 198 110 470 667 486 705 505 497 537 580 780 732 884 787 664 147 52 806 663 842 394 360 476 837 802 782 747 943 ...

result:

points 0.50 jury has the better answer; correct answer = 14376;

Test #22:

score: 19
Acceptable Answer
time: 2ms
memory: 3648kb

input:

999
731 687
673 842
221 812
673 902
239 774
18 251
133 461
396 647
376 819
966 519
30 617
297 574
275 88
926 172
907 465
774 303
10 404
547 728
352 357
549 413
27 309
297 843
573 49
556 523
289 655
769 549
16 581
402 576
411 75
981 413
12 108
850 434
627 353
263 752
165 746
761 856
88 375
312 90
761...

output:

11674 11674
50 918 391 903 74 829 612 956 161 70 421 973 198 630 541 905 318 904 429 889 641 528 371 748 487 121 292 821 235 367 36 997 754 574 494 336 862 980 279 312 384 569 647 668 725 284 900 622 347 34 163 959 724 166 285 443 705 818 736 156 957 535 944 868 993 871 966 183 628 578 872 732 118 8...

result:

points 0.50 jury has the better answer; correct answer = 11674;

Test #23:

score: 19
Acceptable Answer
time: 1ms
memory: 3736kb

input:

987
840 63
459 542
449 461
397 392
585 630
322 108
449 806
10 433
529 449
702 617
674 975
417 156
983 5
746 66
208 232
244 402
162 331
695 175
616 42
528 765
437 100
425 26
96 133
37 91
93 690
317 201
189 128
576 566
847 64
65 684
217 445
214 217
151 369
4 527
91 763
978 87
739 6
802 70
417 786
199 ...

output:

11812 11812
902 196 32 908 188 602 885 679 31 391 529 527 932 652 598 694 528 716 395 374 109 133 929 33 967 734 897 352 906 43 937 415 611 49 394 159 917 440 387 544 892 841 377 982 63 148 588 373 14 941 723 5 574 577 691 411 450 562 777 842 383 886 267 760 933 7 163 455 438 425 776 593 738 126 880...

result:

points 0.50 jury has the better answer; correct answer = 11812;

Test #24:

score: 19
Acceptable Answer
time: 1ms
memory: 3732kb

input:

1000
618 292
281 35
663 995
702 117
25 252
913 959
740 974
985 395
23 397
352 905
932 681
209 542
745 500
346 371
449 506
856 812
664 545
999 23
813 227
554 944
455 541
472 53
224 39
91 484
139 731
620 233
759 253
279 151
857 450
353 400
797 482
63 43
81 516
141 943
382 660
977 45
240 589
267 47
560...

output:

500000 500000
931 907 190 543 109 156 957 332 460 359 339 376 557 337 845 296 263 154 158 993 504 878 847 155 639 592 470 560 629 77 160 642 454 693 516 416 300 445 110 63 885 809 914 913 550 164 981 843 436 608 413 247 349 130 188 266 702 444 900 564 555 940 274 430 23 202 668 681 79 480 768 553 63...

result:

points 0.50 jury has the better answer; correct answer = 500000;

Test #25:

score: 19
Acceptable Answer
time: 0ms
memory: 3704kb

input:

999
871 760
692 751
234 935
861 721
846 760
231 625
667 861
258 596
771 61
876 782
69 799
567 422
927 920
318 235
58 911
26 383
257 606
228 738
476 428
381 292
46 988
144 814
277 532
770 648
217 32
405 941
130 603
146 661
58 503
912 714
377 256
92 637
477 395
88 278
438 294
708 356
906 149
381 140
9...

output:

91036 91036
485 860 758 36 544 929 988 828 549 761 487 566 680 187 800 10 239 202 732 12 270 649 704 754 332 477 379 597 747 55 40 106 356 799 859 108 133 440 934 323 7 837 120 268 969 876 125 694 236 321 240 443 97 41 361 963 752 110 908 20 671 14 718 210 17 342 512 795 619 520 936 584 393 807 15 5...

result:

points 0.50 jury has the better answer; correct answer = 91036;

Test #26:

score: 19
Acceptable Answer
time: 0ms
memory: 5756kb

input:

909
140 106
583 520
460 181
523 659
107 351
900 122
135 31
368 867
262 110
128 579
640 445
14 818
378 341
196 117
350 400
62 348
879 597
318 618
283 37
315 523
239 879
207 458
905 574
35 127
479 883
812 550
342 590
410 624
462 782
422 560
858 526
8 125
215 447
182 360
17 369
803 7
372 219
8 455
1 64...

output:

43956 43956
248 6 446 161 575 290 596 678 13 559 819 889 294 765 92 314 16 108 366 387 685 635 745 522 202 711 146 334 154 437 70 748 620 636 361 459 362 431 236 466 304 750 29 81 476 766 420 261 363 411 454 333 96 323 83 257 640 715 255 659 56 242 665 628 482 814 50 105 1 557 232 170 388 764 758 58...

result:

points 0.50 jury has the better answer; correct answer = 43956;

Test #27:

score: 19
Acceptable Answer
time: 1ms
memory: 3712kb

input:

1000
322 537
402 605
63 899
250 892
64 985
806 42
40 618
948 945
686 85
348 536
451 664
612 443
474 780
352 690
778 812
308 289
958 516
389 284
672 366
556 944
569 496
43 364
484 570
738 954
766 402
935 933
696 214
925 559
889 858
590 219
1000 473
609 580
418 357
271 466
758 929
682 878
678 778
917 ...

output:

250998 250998
737 477 568 937 400 664 996 380 10 754 258 535 467 523 4 293 366 386 524 300 654 776 745 142 131 66 844 205 164 931 86 391 837 815 924 609 441 656 970 982 639 515 444 644 870 899 626 344 404 548 192 199 379 27 911 93 572 417 437 843 200 564 284 476 346 666 204 946 104 189 220 422 649 5...

result:

points 0.50 jury has the better answer; correct answer = 250998;

Test #28:

score: 19
Acceptable Answer
time: 2ms
memory: 5964kb

input:

1000
944 65
357 755
504 31
900 759
916 234
547 41
761 831
282 858
855 983
770 797
539 473
492 455
18 323
915 294
690 69
935 463
701 665
259 215
102 55
5 876
375 735
810 578
371 785
687 757
213 649
307 658
988 462
610 810
870 847
521 97
637 589
173 702
492 426
16 872
412 705
667 778
592 943
810 872
1...

output:

127496 127496
280 956 25 858 380 397 657 207 628 842 361 762 54 844 681 714 603 585 388 158 292 331 123 683 301 802 452 869 418 555 793 389 147 506 120 572 889 838 36 623 629 330 480 848 958 807 542 167 262 423 420 911 370 660 34 316 990 876 605 195 65 288 612 735 886 232 8 419 525 986 171 650 114 5...

result:

points 0.50 jury has the better answer; correct answer = 127496;

Test #29:

score: 38
Accepted
time: 1ms
memory: 4048kb

input:

1000
275 786
275 833
193 275
948 275
409 275
275 988
539 275
275 267
187 275
367 275
556 275
425 275
295 275
275 763
587 275
73 275
40 275
275 709
912 275
64 275
847 275
275 979
275 520
239 275
701 275
477 275
275 454
356 275
906 275
420 275
814 275
739 275
30 275
275 95
502 275
550 275
275 230
275 ...

output:

1998 1998
552 957 682 387 323 843 186 946 473 987 676 478 101 103 632 941 667 959 555 690 315 650 98 736 966 272 419 191 214 95 55 136 913 278 872 348 661 771 43 833 508 766 39 845 240 918 105 470 574 949 235 944 860 232 31 919 744 612 168 758 139 964 703 912 491 811 227 250 869 969 780 746 898 447 ...

result:

points 1.0 correct answer = 1998; correct answer = 1998;

Test #30:

score: 19
Acceptable Answer
time: 0ms
memory: 5828kb

input:

989
740 463
740 19
531 322
740 544
177 531
531 147
937 531
740 365
876 740
750 740
67 531
881 740
740 838
765 740
740 304
344 740
22 531
740 176
491 531
772 740
531 187
833 740
531 933
372 740
740 840
740 295
740 685
740 769
452 531
740 471
740 766
740 846
531 971
740 590
740 212
720 740
721 740
166...

output:

2962 2962
764 800 346 885 570 600 914 335 406 398 747 881 679 294 652 455 56 648 779 105 359 513 369 821 283 424 906 375 912 977 942 414 802 789 374 297 522 882 798 891 770 248 786 541 932 301 502 710 874 918 608 306 830 423 926 17 934 426 559 703 212 20 415 839 857 896 738 561 966 780 887 744 515 3...

result:

points 0.50 jury has the better answer; correct answer = 2962;

Test #31:

score: 19
Acceptable Answer
time: 1ms
memory: 3944kb

input:

1000
215 913
18 659
755 775
60 282
156 687
282 591
797 850
448 282
577 484
637 282
345 913
85 289
634 695
775 746
475 362
489 190
894 269
913 696
831 21
92 547
913 795
267 579
982 839
547 571
21 219
547 759
770 298
258 364
85 878
298 279
85 81
643 504
775 643
18 524
775 952
263 770
775 611
587 775
2...

output:

7958 7958
960 97 664 191 26 616 572 845 501 753 160 623 945 229 597 312 675 713 359 181 852 545 927 202 327 544 441 762 876 336 556 985 585 929 529 630 314 951 923 289 577 931 722 842 192 377 281 918 220 604 116 745 824 979 652 286 31 543 189 656 989 705 901 295 122 526 388 98 429 946 21 284 9 79 32...

result:

points 0.50 jury has the better answer; correct answer = 7958;

Test #32:

score: 19
Acceptable Answer
time: 1ms
memory: 3716kb

input:

888
310 287
55 464
55 160
2 713
73 237
427 193
2 61
679 55
45 73
117 73
73 432
55 785
797 861
704 55
312 861
397 73
474 317
73 43
434 474
213 861
566 801
861 301
230 73
737 2
134 566
427 337
480 55
11 73
577 861
427 114
674 474
887 185
429 427
861 723
316 474
861 819
206 732
73 346
568 55
887 20
2 8...

output:

4288 4288
2 797 756 803 293 161 332 888 272 89 325 193 281 243 144 153 850 38 35 145 98 576 779 867 715 496 278 704 732 366 77 856 159 611 598 178 734 652 104 65 553 167 287 707 459 387 75 259 809 361 465 885 3 537 62 137 76 47 43 749 489 216 357 887 294 735 441 880 474 706 813 389 458 554 609 126 5...

result:

points 0.50 jury has the better answer; correct answer = 4288;

Test #33:

score: 19
Acceptable Answer
time: 1ms
memory: 3736kb

input:

1000
60 327
715 322
13 49
48 263
3 523
770 46
551 160
751 160
580 859
392 466
560 282
461 86
339 127
644 539
530 202
605 852
511 550
563 309
425 92
22 17
708 583
134 156
449 225
274 300
578 569
579 335
729 539
464 579
510 79
77 497
593 497
614 636
555 942
8 13
920 67
957 412
613 632
906 649
579 399
...

output:

9628 9628
293 315 944 573 347 459 872 502 595 164 380 150 898 223 763 257 346 336 472 183 176 110 250 525 730 98 997 211 985 948 447 135 359 692 120 298 465 395 673 803 398 918 272 62 571 741 544 760 115 187 647 303 931 737 216 549 835 270 252 441 910 121 156 564 118 129 292 105 903 332 200 621 619 ...

result:

points 0.50 jury has the better answer; correct answer = 9628;

Test #34:

score: 19
Acceptable Answer
time: 1ms
memory: 3712kb

input:

987
543 539
482 744
58 699
322 99
741 808
107 99
248 230
247 917
934 869
438 424
248 258
393 578
632 704
786 418
683 882
679 730
849 46
203 968
33 972
155 223
799 154
154 291
527 867
424 739
731 323
424 484
158 86
452 679
799 686
138 818
672 600
424 853
424 247
331 261
734 772
754 780
15 103
482 552...

output:

6554 6554
605 850 204 321 389 861 824 163 8 116 966 857 702 179 885 981 256 723 895 759 692 635 166 542 63 318 264 929 259 42 563 129 338 439 599 859 362 783 123 842 587 823 295 685 185 372 953 290 811 126 946 570 252 286 48 839 369 949 227 892 761 855 660 99 684 343 180 812 19 250 897 786 92 815 89...

result:

points 0.50 jury has the better answer; correct answer = 6554;

Test #35:

score: 19
Acceptable Answer
time: 1ms
memory: 3660kb

input:

975
645 307
416 645
377 175
639 842
527 377
591 444
134 7
42 569
305 194
598 758
7 209
850 175
598 975
471 393
303 444
614 320
126 598
671 194
444 564
728 444
338 598
324 947
733 891
906 515
124 752
175 470
752 243
727 645
547 455
670 499
687 444
590 444
662 552
7 175
444 39
349 444
597 444
473 639
...

output:

5278 5278
589 254 597 772 241 203 587 743 676 289 98 77 694 616 121 975 93 220 892 1 450 527 424 373 238 807 909 494 542 459 591 886 43 341 123 660 795 3 420 479 19 391 304 466 268 492 149 283 910 641 48 166 403 139 753 913 365 414 15 554 615 546 667 561 21 437 115 325 665 64 829 805 707 18 106 157 ...

result:

points 0.50 jury has the better answer; correct answer = 5278;

Test #36:

score: 19
Acceptable Answer
time: 1ms
memory: 3724kb

input:

1000
538 932
941 662
61 662
90 217
276 538
721 260
75 979
217 53
235 684
769 662
538 497
662 355
414 662
147 217
235 309
44 235
217 689
156 217
498 235
52 217
217 617
709 662
662 510
306 662
583 752
578 662
721 258
662 603
217 249
286 235
734 75
662 165
291 721
721 482
917 110
340 235
538 800
217 42...

output:

3906 3906
279 963 533 492 514 712 132 672 728 4 555 197 204 458 320 118 535 187 669 218 314 794 843 519 638 523 857 329 907 95 852 795 640 497 81 288 371 383 566 982 188 395 579 86 494 938 463 9 431 883 845 781 742 112 109 133 594 316 536 667 389 805 502 392 829 888 721 988 910 895 700 723 190 650 2...

result:

points 0.50 jury has the better answer; correct answer = 3906;

Test #37:

score: 19
Acceptable Answer
time: 0ms
memory: 5716kb

input:

1000
620 802
417 303
67 87
300 180
67 880
7 453
826 481
720 505
67 754
841 823
67 35
592 402
940 481
599 438
5 67
681 353
890 399
438 732
542 667
258 399
502 667
583 530
399 391
479 949
210 742
337 681
232 512
417 996
417 170
417 97
870 567
470 620
4 849
186 870
559 348
702 288
374 417
681 362
67 99...

output:

6546 6546
329 871 580 869 678 59 864 298 273 745 991 395 868 589 987 108 278 929 170 781 619 515 240 526 249 758 505 128 715 425 327 638 158 219 859 453 843 70 312 39 275 416 369 520 937 686 86 260 417 462 314 576 497 602 486 242 946 540 575 251 670 472 454 528 736 441 579 726 778 705 724 693 196 75...

result:

points 0.50 jury has the better answer; correct answer = 6546;

Test #38:

score: 19
Acceptable Answer
time: 0ms
memory: 3712kb

input:

1000
520 185
785 97
15 774
521 437
421 163
906 123
869 429
520 538
459 70
97 943
178 39
475 97
742 637
705 417
502 520
57 705
487 123
627 97
469 59
403 123
165 437
123 264
369 538
231 57
786 715
96 15
762 794
437 744
692 893
794 437
135 437
794 74
765 9
305 57
924 15
57 965
469 559
520 163
690 449
1...

output:

4626 4626
924 577 879 256 25 81 103 594 23 728 312 158 301 881 829 907 763 371 980 956 438 780 90 280 950 939 472 550 840 538 63 181 497 243 990 12 411 287 400 123 445 875 634 169 201 131 502 314 509 963 1000 8 341 101 378 78 327 82 519 74 375 126 383 636 619 121 604 722 140 3 267 988 463 434 571 4 ...

result:

points 0.50 jury has the better answer; correct answer = 4626;

Test #39:

score: 19
Acceptable Answer
time: 1ms
memory: 3768kb

input:

999
683 443
89 76
60 664
625 39
3 811
337 527
687 154
956 443
695 664
702 100
290 957
20 445
154 397
260 823
347 154
620 299
339 664
154 851
170 620
397 781
68 154
155 264
823 555
281 445
620 697
397 213
815 75
811 896
953 397
290 997
154 13
677 664
9 823
527 166
544 154
989 445
11 39
75 570
535 39
...

output:

4914 4914
661 817 79 24 618 231 122 357 492 118 703 922 512 10 937 729 409 84 474 535 617 985 609 347 799 412 129 670 154 845 137 369 475 958 71 14 303 566 379 468 338 227 908 710 121 604 124 757 329 30 458 457 691 667 438 904 295 408 411 668 498 594 419 78 862 980 109 969 110 741 501 740 116 586 44...

result:

points 0.50 jury has the better answer; correct answer = 4914;

Test #40:

score: 19
Acceptable Answer
time: 1ms
memory: 3684kb

input:

900
825 630
478 117
271 20
293 597
588 280
290 348
412 433
387 597
269 638
841 101
395 379
30 742
836 550
447 438
714 478
535 872
816 386
124 378
358 519
407 843
628 82
875 108
282 500
690 811
465 475
490 629
786 654
287 238
381 686
821 193
299 425
252 626
164 471
195 293
159 408
315 443
166 843
293...

output:

7882 7882
873 424 404 56 449 46 697 545 259 276 789 361 292 432 237 692 628 844 588 783 436 4 367 407 442 87 86 138 673 602 624 447 739 798 557 173 633 761 765 604 483 591 874 346 405 335 340 258 28 161 847 544 784 210 289 779 567 719 23 705 208 521 326 155 342 639 102 577 889 659 808 136 899 803 75...

result:

points 0.50 jury has the better answer; correct answer = 7882;

Test #41:

score: 19
Acceptable Answer
time: 1ms
memory: 4000kb

input:

888
235 292
649 771
880 641
57 46
480 401
401 762
587 856
432 475
428 95
698 807
294 713
179 818
166 730
118 714
722 764
745 484
258 474
597 394
822 301
306 202
774 847
643 886
663 772
235 78
734 243
171 718
173 357
539 681
816 186
225 335
702 427
662 626
810 886
258 865
95 722
258 38
764 307
880 60...

output:

10654 10654
190 280 338 178 498 880 201 789 726 334 185 128 359 725 65 422 520 576 529 663 679 536 527 748 95 377 274 861 828 284 151 776 434 75 166 483 104 868 749 127 186 481 355 506 569 517 418 325 411 539 706 61 482 467 156 739 554 211 197 565 625 773 290 462 41 474 792 745 603 233 720 854 737 1...

result:

points 0.50 jury has the better answer; correct answer = 10654;

Test #42:

score: 19
Acceptable Answer
time: 0ms
memory: 3876kb

input:

512
89 508
46 478
502 121
413 67
372 22
146 217
337 450
456 321
511 445
275 248
475 32
1 357
59 130
149 372
289 407
47 351
23 102
7 271
486 415
197 243
270 107
68 176
344 429
222 341
200 294
324 291
451 379
331 491
458 30
307 70
326 179
118 400
348 133
121 188
396 310
135 39
43 69
371 113
202 494
46...

output:

7190 7190
220 233 316 219 359 360 90 415 381 247 282 189 285 151 491 181 489 135 250 426 417 263 192 245 99 148 314 73 322 106 298 103 371 201 270 271 343 431 96 225 504 406 214 134 510 429 315 413 348 447 64 456 224 133 462 155 347 126 286 388 255 418 439 142 100 18 4 111 451 339 257 279 104 145 50...

result:

points 0.50 jury has the better answer; correct answer = 7190;

Test #43:

score: 19
Acceptable Answer
time: 1ms
memory: 3752kb

input:

1000
749 604
537 255
155 171
608 433
9 347
189 482
269 714
955 137
134 903
730 26
18 478
563 64
722 990
270 587
237 29
67 419
792 574
587 59
797 48
581 91
826 262
87 589
417 649
10 59
693 668
400 678
639 826
541 590
925 96
319 537
348 675
615 429
73 335
987 150
362 243
49 125
169 507
207 266
318 702...

output:

15930 15930
457 394 506 403 131 238 769 421 916 617 921 922 509 312 412 362 528 166 924 990 626 199 604 68 475 767 774 735 189 858 565 844 722 270 368 759 846 925 751 35 631 210 181 356 659 366 599 796 706 966 881 766 355 566 95 559 779 911 39 474 672 935 351 993 482 266 907 995 413 828 786 80 272 5...

result:

points 0.50 jury has the better answer; correct answer = 15930;

Test #44:

score: 19
Acceptable Answer
time: 1ms
memory: 3640kb

input:

513
505 334
136 410
403 254
205 286
43 133
274 127
257 389
355 335
182 30
494 221
134 365
354 468
293 204
482 326
418 489
221 458
471 22
173 176
71 461
348 194
190 81
434 459
432 123
420 260
207 483
83 494
506 379
302 184
340 510
465 466
159 57
418 392
77 110
164 436
246 353
462 363
64 72
298 58
177...

output:

7206 7206
362 336 192 57 383 304 295 496 442 463 325 73 339 395 112 164 512 107 262 292 416 425 481 48 218 225 228 466 277 147 400 202 118 484 111 123 136 196 150 345 247 329 334 103 235 234 265 78 457 353 204 143 254 121 375 501 193 25 364 140 28 209 239 227 170 407 71 333 148 102 68 36 447 502 198...

result:

points 0.50 jury has the better answer; correct answer = 7206;

Test #45:

score: 19
Acceptable Answer
time: 1ms
memory: 3656kb

input:

1000
814 905
347 904
611 989
779 507
175 845
663 597
327 707
175 847
972 737
685 985
895 758
55 557
402 565
323 109
921 497
426 100
567 602
102 807
542 988
123 597
558 980
275 818
437 639
426 326
90 91
715 139
697 369
942 392
958 92
923 991
9 820
93 748
797 589
403 681
821 561
908 344
1 730
18 389
1...

output:

9094 9094
359 144 67 963 807 479 645 735 563 73 250 476 268 229 854 952 581 733 344 353 987 256 869 673 299 580 421 207 263 296 116 270 798 10 518 137 545 618 203 465 78 33 387 560 568 934 237 11 310 692 587 797 543 468 286 411 991 219 871 550 898 134 966 77 146 377 850 424 272 972 176 511 933 302 3...

result:

points 0.50 jury has the better answer; correct answer = 9094;

Test #46:

score: 19
Acceptable Answer
time: 0ms
memory: 5668kb

input:

999
41 215
96 23
802 926
318 19
569 7
271 362
91 295
486 920
491 471
882 754
357 784
106 794
986 763
846 697
361 297
309 295
12 291
726 989
463 707
301 712
569 44
295 379
680 724
17 482
398 562
620 709
473 616
616 521
468 885
491 350
486 781
646 169
680 500
762 602
302 806
271 982
965 51
587 814
455...

output:

5748 5748
42 353 850 743 898 563 826 681 838 761 977 754 668 980 160 972 589 830 920 618 859 218 940 757 642 565 644 570 245 899 185 594 338 699 494 669 312 798 936 90 971 574 204 631 161 651 276 924 587 308 719 863 29 835 716 120 334 188 240 295 619 30 629 437 150 705 811 133 573 875 203 301 64 520...

result:

points 0.50 jury has the better answer; correct answer = 5748;

Test #47:

score: 19
Acceptable Answer
time: 1ms
memory: 3964kb

input:

1000
553 877
155 71
446 981
20 558
254 673
558 1
322 83
553 933
597 810
155 569
585 246
836 254
728 203
55 558
1 847
23 1
775 246
739 246
615 246
558 446
997 810
619 558
810 574
560 203
83 740
446 887
246 364
885 558
203 850
1 445
203 269
830 558
254 255
707 155
925 1
246 72
900 254
1 164
232 203
55...

output:

3794 3794
752 728 333 83 967 437 510 908 346 785 223 949 403 837 657 471 627 987 841 444 318 360 548 285 29 399 755 420 25 308 710 326 395 726 993 747 325 986 88 788 61 647 539 674 468 583 390 274 283 119 65 832 489 350 992 332 273 866 505 838 918 300 79 221 812 524 595 665 347 140 417 774 757 594 6...

result:

points 0.50 jury has the better answer; correct answer = 3794;

Subtask #3:

score: 25
Acceptable Answer

Dependency #1:

50%
Acceptable Answer

Dependency #2:

50%
Acceptable Answer

Test #48:

score: 25
Acceptable Answer
time: 95ms
memory: 11180kb

input:

90909
17758 575
3979 26221
88569 9552
14110 25350
82691 8857
4392 3854
29926 34058
58734 57918
79463 1578
72922 88952
29022 15060
7400 82837
22366 32557
40522 1551
11803 21395
67987 61163
61666 33213
76732 71510
12690 4331
45264 45547
33241 3589
42298 60029
175 16809
87099 33650
36724 90662
17339 82...

output:

1514350 1514350
18458 47702 22299 15362 62939 14965 85419 30348 61105 80192 46624 54213 72062 65678 63919 24168 70109 25940 89747 44816 71082 12697 54288 11572 64995 23234 62179 90331 83020 39530 52235 88041 16299 59720 33932 33159 75643 44543 52712 33398 9204 52051 65679 44823 77926 39412 43690 592...

result:

points 0.50 jury has the better answer; correct answer = 1514350;

Test #49:

score: 25
Acceptable Answer
time: 99ms
memory: 12100kb

input:

99999
54092 13956
13184 61256
33359 49486
66333 35721
18952 38623
44461 32240
7677 43577
10072 69601
51823 90760
3409 2346
35171 14267
11756 4958
1279 98439
6663 79391
41211 680
60131 26805
35555 6553
11752 25265
78423 9479
35573 84992
7615 93132
27092 45858
58284 43654
82163 19951
44496 80808
30235...

output:

2159862 2159862
48104 23550 97481 93824 45951 48194 17843 83924 37362 65267 87754 70464 30922 74040 91771 11471 34358 39254 90307 62400 88321 49095 68337 30212 23510 6698 35214 53294 68063 59979 53492 71320 81310 36606 11829 22580 6858 22712 19431 91357 58784 38620 44849 5191 53673 37517 78854 64018...

result:

points 0.50 jury has the better answer; correct answer = 2159862;

Test #50:

score: 25
Acceptable Answer
time: 107ms
memory: 11760kb

input:

100000
8397 23570
15100 5651
49763 76387
86170 31489
73912 4373
40057 1373
44267 59312
8016 9571
69847 58672
6937 26585
59707 54569
11150 71161
79711 85747
50827 77535
53619 30774
40442 87404
174 11719
28697 64997
99081 58676
97130 34559
36772 82010
93606 4909
50756 30487
45617 4455
73129 58420
7307...

output:

1952940 1952940
50223 14907 92565 49376 8038 1713 83402 31132 50112 63563 16844 36544 37029 57857 59107 45402 15829 12935 54273 82288 80248 5630 35756 34923 15194 31835 65963 42404 8948 85536 95025 27405 836 8770 68728 21395 43497 38783 99007 65671 23715 37307 63777 92137 53337 9520 35690 45718 7533...

result:

points 0.50 jury has the better answer; correct answer = 1952940;

Test #51:

score: 25
Acceptable Answer
time: 66ms
memory: 10348kb

input:

77777
49943 35215
22761 10315
63949 60762
4297 59709
45833 48233
24906 70063
1043 24637
48007 35750
52453 36493
22069 3606
16535 2881
42152 50952
62168 47796
55820 54249
31137 17726
71771 10232
23669 19313
25535 61808
43055 75073
27628 61062
3909 15503
5234 8030
43698 40315
47559 43005
42986 14117
3...

output:

1605682 1605682
26173 73932 13031 75153 6173 38411 51397 33881 39529 73063 15032 76998 61416 29693 72993 34166 47268 5661 67627 46271 1246 36331 31636 76784 23709 51399 6579 7707 30043 1066 77692 73999 50822 32597 7020 2887 74557 37508 65895 69662 39181 20997 67065 48251 60243 58000 66939 49669 1709...

result:

points 0.50 jury has the better answer; correct answer = 1605682;

Test #52:

score: 25
Acceptable Answer
time: 84ms
memory: 11928kb

input:

98765
26164 11043
13421 94996
26702 23597
51201 48250
67973 352
95881 8874
26458 74693
39046 88648
56736 47954
12216 65746
47531 21188
53614 90889
75649 88093
12503 85226
13085 17574
3182 88290
7886 11181
74066 20694
68687 85540
2669 95364
26971 65560
21145 71952
645 80289
96522 98194
6246 27803
294...

output:

1740764 1740764
71054 35910 68722 71653 68636 94083 58330 46146 69481 37081 8164 52620 49060 67711 41018 75238 30852 26149 9236 81781 33972 87746 23661 21706 88673 96538 53522 49072 73334 82480 70376 97287 49174 55429 66304 14812 56358 64736 33716 70529 2084 95735 75815 76069 3968 64339 55160 58650 ...

result:

points 0.50 jury has the better answer; correct answer = 1740764;

Test #53:

score: 25
Acceptable Answer
time: 93ms
memory: 10868kb

input:

88888
18007 20138
8462 60324
76528 52591
4898 80575
65204 88644
39569 56354
74132 32611
76206 80221
30915 52745
6143 32530
37410 31142
59677 25661
76412 76063
6660 37530
45897 15591
71856 63855
1803 81486
33589 37579
38044 36868
51718 27393
56500 62186
50198 1745
24687 49671
56093 47676
2749 5510
41...

output:

1835832 1835832
46030 47609 24938 28351 20192 2921 12810 38063 29093 37804 12931 48845 70274 53487 5755 86918 68779 10409 77446 44893 76355 56005 35924 49449 3824 3361 31533 69527 13430 81494 83627 86323 36604 8936 30535 35414 77936 4937 53037 44113 63225 16333 68957 11403 73930 36416 29459 63573 52...

result:

points 0.50 jury has the better answer; correct answer = 1835832;

Test #54:

score: 25
Acceptable Answer
time: 93ms
memory: 11388kb

input:

50000
14916 47169
33646 11209
38695 46961
47666 40483
17572 38925
37411 36620
4463 17026
40132 10341
17528 19481
4578 35441
46407 23708
41583 49270
1195 24736
44669 15788
3517 5379
3133 19387
32077 35038
28532 44617
35666 10962
43195 29214
27865 27035
110 63
43623 37912
49803 3591
32881 6416
13331 6...

output:

1250000000 1250000000
24663 45290 48457 12619 6196 5282 6225 14016 1304 33184 22034 35789 21835 29811 9908 46026 17414 8714 16035 10593 11275 15963 31313 25818 43887 45064 21498 26938 33477 42009 22942 17471 33216 25405 30818 25781 38669 41505 908 21930 30656 21455 44226 11406 4201 26695 14448 28078...

result:

points 0.50 jury has the better answer; correct answer = 1250000000;

Test #55:

score: 25
Acceptable Answer
time: 277ms
memory: 18980kb

input:

100000
34635 44783
29898 23005
11921 93048
26316 97267
76312 78003
44678 65267
92998 33803
18207 56360
97228 34583
51479 61204
15154 52716
55424 6281
26461 50794
52385 57566
45012 286
61533 53131
70762 40867
44304 47410
8330 48137
471 45034
86876 4416
8219 69916
90129 69737
91513 22330
28128 77098
9...

output:

5000000000 5000000000
61527 5179 99385 28611 25417 85333 6878 6987 24314 21920 58420 78830 9396 17650 27045 48649 16955 90833 27121 84995 53723 14722 8520 3080 62665 1194 77749 43922 26167 60443 75521 41140 4544 62508 72405 57455 62895 26888 34256 82961 9805 23168 42618 39992 35815 96579 18541 81125...

result:

points 0.50 jury has the better answer; correct answer = 5000000000;

Test #56:

score: 25
Acceptable Answer
time: 211ms
memory: 15392kb

input:

100000
57874 74848
75513 33053
8252 73504
54317 83788
60111 13340
31363 50361
18099 58345
84161 14657
44767 33004
7985 30623
55979 10992
6046 17013
68042 57124
66489 22815
81861 10841
20185 88719
72124 59308
43981 25485
93741 19371
67292 25574
39133 49194
55685 66197
97964 53704
64571 75054
40228 42...

output:

2504160170 2504160170
78902 28536 21342 82632 55515 23766 29339 22850 99831 80818 22461 11340 3294 65384 48289 17165 6136 18234 60145 6446 84956 82929 94092 73769 93174 48939 75080 62524 94912 58064 55123 28490 69304 43891 47215 750 62245 51603 26516 95219 22415 45499 85461 97438 96274 1506 3506 393...

result:

points 0.50 jury has the better answer; correct answer = 2504160170;

Test #57:

score: 25
Acceptable Answer
time: 203ms
memory: 14072kb

input:

98765
81026 87591
95939 42505
22772 71253
58032 39973
83905 46725
9616 51346
90127 71702
16798 22229
74466 35601
53002 94854
14026 29206
36395 41515
19908 51464
55451 80213
41927 56419
17761 68704
57675 88162
39109 27245
78393 53771
73516 97673
10058 27149
60582 32042
63577 2879
11137 97742
19593 62...

output:

1634005140 1634005140
61836 35043 6023 44290 5504 42086 58647 76402 39366 14164 76624 40592 8757 6258 65638 15236 6698 32546 11694 328 84817 49113 97514 82249 36034 84618 25476 69034 27425 92158 7398 79875 59386 22706 73553 53465 85520 94352 61605 10054 38102 90017 70269 18083 13427 81741 15955 6090...

result:

points 0.50 jury has the better answer; correct answer = 1634005140;

Test #58:

score: 25
Acceptable Answer
time: 191ms
memory: 13200kb

input:

100000
21659 3974
12194 694
75940 8912
96273 38672
95780 34408
14755 83593
74731 36134
456 71307
65344 26234
48183 38993
5303 37248
4527 14460
84382 77887
36991 47193
64329 27470
2326 58685
26601 13997
9625 46107
10647 16094
25195 95211
85068 49658
17059 9840
38230 15203
35339 51305
43188 31525
8652...

output:

830383780 830383780
49092 75542 35497 94374 84752 47683 65501 87138 28838 15368 10570 48851 16538 46103 9632 2257 83145 4444 38570 60874 40417 82378 9949 97902 8980 4276 79266 38119 36186 37929 1417 21275 74175 86274 87610 45675 67159 18351 25055 62262 92912 46269 3437 33741 31883 80054 49473 33441 ...

result:

points 0.50 jury has the better answer; correct answer = 830383780;

Test #59:

score: 25
Acceptable Answer
time: 124ms
memory: 12340kb

input:

100000
76978 82392
95351 80699
72534 98914
55636 92340
51114 53079
87369 16897
13382 68476
91961 67058
30326 38260
92346 69124
13572 17998
26610 62603
19103 76290
63391 82287
10466 86694
74552 96544
81984 81396
17931 31839
75637 24199
42173 60079
98253 95511
88390 76077
78642 92871
54168 53240
66642...

output:

81728820 81728820
48119 59639 82210 70567 60458 61916 43816 22404 44657 31986 35967 26194 53570 94722 59111 59086 97903 43421 79292 68414 93980 30714 91669 75586 40136 58077 49065 925 85169 75456 79321 5587 62698 40714 30300 98479 79048 7351 87039 81751 90133 87950 74058 56160 796 78477 31783 1052 6...

result:

points 0.50 jury has the better answer; correct answer = 81728820;

Test #60:

score: 50
Accepted
time: 45ms
memory: 21996kb

input:

100000
6298 68124
6298 92167
43605 6298
20237 6298
63882 6298
17208 6298
6298 8987
35761 6298
6298 37845
6298 12511
6298 84393
6298 4322
6298 70916
77435 6298
6298 13009
3497 6298
6298 32572
6298 97863
3877 6298
6298 3043
6298 89660
6298 61248
77168 6298
6298 74790
39750 6298
6298 3914
6298 73268
44...

output:

199998 199998
60733 83016 6015 59138 74136 81181 47781 65908 12360 4870 353 81254 35321 70831 89109 20949 3523 12359 41809 82711 44472 51478 72432 80783 34330 73496 85597 88093 83513 84255 22820 642 45095 92138 64889 11209 94190 11436 31444 59956 75446 57350 47441 86007 23377 54492 93533 29271 18695...

result:

points 1.0 correct answer = 199998; correct answer = 199998;

Test #61:

score: 25
Acceptable Answer
time: 48ms
memory: 14908kb

input:

100000
42523 18318
78023 33382
42523 74647
51119 93379
42523 74276
35982 31079
86097 73375
73375 37592
88260 78023
51119 16060
51119 41589
31079 76077
78023 895
31079 80768
33854 73375
81020 31079
73375 23846
73375 32020
72275 51119
78023 20372
91098 78023
76149 73375
31079 10682
65827 51119
31079 6...

output:

359886 359886
14928 30601 42846 98906 22844 32127 22125 34056 86267 73617 71105 93530 20454 32069 97875 55355 12611 62507 37963 48974 23665 10584 7639 98923 72506 5458 38768 26384 65731 55864 79103 12028 28187 27717 8355 36691 77279 69570 96096 67624 88596 59319 43787 67862 13278 74233 7228 96412 21...

result:

points 0.50 jury has the better answer; correct answer = 359886;

Test #62:

score: 25
Acceptable Answer
time: 52ms
memory: 12620kb

input:

100000
61154 13087
5895 20067
53687 86061
65229 2888
82566 2913
77544 1083
64861 21491
60935 82827
94490 81164
2751 80045
36174 20082
23301 28396
4507 38899
3671 75923
97876 10985
1083 8128
94690 61154
83849 67805
14978 44250
53687 13493
82995 30707
79102 65229
80669 5895
60831 14829
64861 31115
326...

output:

932808 932808
47350 32006 20204 14646 31485 13834 97886 97105 74780 73515 68969 6539 62088 92449 97776 90320 92927 96885 92163 87006 74791 68508 98100 46669 72655 63056 10411 61145 3430 55553 70410 62815 18669 76517 28651 44818 83181 18671 79989 16968 89037 56318 75048 7228 75537 4331 95046 78636 39...

result:

points 0.50 jury has the better answer; correct answer = 932808;

Test #63:

score: 25
Acceptable Answer
time: 45ms
memory: 12308kb

input:

93829
47115 19407
23207 63386
17281 25733
40288 38302
337 2745
91558 51272
22370 40783
13789 52003
37083 8059
27675 38898
16630 62411
5446 7537
48460 75134
75503 42782
39428 2789
53303 44469
17049 13789
33819 78840
93481 56041
45430 54823
47115 47902
59366 26785
68439 80701
88748 31652
25730 88748
8...

output:

837534 837534
34715 1391 84620 10697 50384 91017 92124 52284 72221 67896 1640 28779 21504 3623 77067 77620 31972 84715 82617 33141 63161 14935 52585 53611 58844 50915 71953 84821 19836 13895 48209 59120 33746 84078 61897 86065 5649 90550 19244 85816 39065 64349 1109 65433 45759 65419 35585 92535 854...

result:

points 0.50 jury has the better answer; correct answer = 837534;

Test #64:

score: 25
Acceptable Answer
time: 56ms
memory: 12440kb

input:

100000
6074 30016
92873 16202
89382 94763
84451 61695
55410 77311
70734 1348
84717 93254
322 16517
36660 36555
19763 29256
45432 79846
56371 47603
1293 45667
80748 61938
60378 65283
7214 68770
33315 41354
19205 30453
85874 7272
6461 92941
21152 40823
31531 70537
88385 43025
62239 37094
76000 64945
3...

output:

1209576 1209576
73721 7502 60340 78043 91233 54011 67671 49178 97715 98619 75815 62841 32151 85576 86325 91032 19532 67288 85491 99199 73464 61655 97117 80106 96836 87068 91796 34109 30676 5796 26378 99580 56811 29707 70742 16859 20059 79479 82443 89423 91436 52861 37689 44605 35667 61714 49513 2712...

result:

points 0.50 jury has the better answer; correct answer = 1209576;

Test #65:

score: 25
Acceptable Answer
time: 57ms
memory: 12736kb

input:

100000
62417 92075
9076 90574
1978 20625
80303 97502
99109 81465
6723 90574
85715 28319
10212 82521
67762 54591
7926 61407
34194 58080
94103 50110
95676 49819
66386 38478
95660 19111
66186 81032
97417 34022
66146 26540
57859 22135
31461 26768
14198 72129
36051 71315
68973 73771
8786 72861
17058 5867...

output:

1179808 1179808
47424 90575 52700 33915 6589 4359 94261 1332 22811 1432 58215 93051 41402 49743 39752 94117 337 24818 97425 82890 98920 82134 21965 7898 13621 42828 77490 60907 43633 89507 79773 7099 6900 2908 7491 58579 63044 18909 26787 45290 80622 98962 67652 27286 32034 81371 27426 65161 86429 4...

result:

points 0.50 jury has the better answer; correct answer = 1179808;

Test #66:

score: 25
Acceptable Answer
time: 45ms
memory: 12572kb

input:

93737
25805 12771
58579 81355
40517 64871
32105 61687
7811 38363
39 60019
92788 69703
80392 8638
69458 60914
28508 74958
44040 33277
76080 88615
32105 2051
31640 56251
12235 44072
7811 33026
28297 3146
74710 32807
37813 57534
16768 61620
48071 91372
12742 56251
61620 3372
22308 39
80509 53749
34275 ...

output:

676668 676668
7202 9798 27427 7153 54502 46953 15544 24084 59788 49726 26536 14183 82653 75316 35681 10131 90493 34926 36941 30111 86243 7311 31997 59981 41099 58908 41342 12068 92546 4350 39719 39787 64432 25461 93251 33260 74005 56454 91850 35055 78682 46439 61010 17831 40961 37349 25839 70858 645...

result:

points 0.50 jury has the better answer; correct answer = 676668;

Test #67:

score: 25
Acceptable Answer
time: 32ms
memory: 12852kb

input:

73820
68064 38747
62935 55677
38747 58570
22710 4111
65275 38747
35710 48769
38747 23670
72818 38747
34638 11917
38747 33628
38747 66577
56980 38923
38747 71252
11366 67900
60971 38923
38747 36433
38747 56366
22710 7426
5505 38747
60963 34638
50309 38923
22710 40719
18272 11366
5124 22710
66588 3874...

output:

308338 308338
22021 25689 72159 23050 53185 28619 27262 46596 51189 10821 23127 25551 13466 46847 6745 61511 12850 49243 9393 39713 46778 62237 68184 53841 69925 54964 68093 34921 22908 9488 26675 41749 44806 60530 22041 17154 12044 7579 24751 21480 17837 42000 13680 22575 1204 25665 58699 68990 557...

result:

points 0.50 jury has the better answer; correct answer = 308338;

Test #68:

score: 25
Acceptable Answer
time: 46ms
memory: 11232kb

input:

84739
27645 6266
38069 44689
82910 62243
64459 18141
3766 67772
79199 63315
6984 83607
33618 26140
3281 34449
77905 74209
39039 13877
27099 50860
78270 68531
17315 13537
9539 48165
71932 81912
3093 55744
50723 28194
56519 2659
41178 15309
66588 12487
76725 69893
39845 82843
82370 15791
12054 72466
4...

output:

943500 943500
26809 653 20107 18238 35331 36286 15686 77723 30868 19423 31613 21711 65827 39565 39789 77095 6986 25689 56235 70694 78547 48003 5359 54528 83348 25681 44608 214 79795 21971 23201 55774 28527 71722 32301 15270 63318 66349 78251 12651 3291 17070 78080 21351 36698 70942 82437 19445 25023...

result:

points 0.50 jury has the better answer; correct answer = 943500;

Test #69:

score: 25
Acceptable Answer
time: 49ms
memory: 12488kb

input:

100000
36497 69443
57547 46832
48779 2175
24154 77660
49565 41399
52180 80166
2105 56691
37345 33567
2041 26971
41967 16118
78293 78726
91173 29725
93733 45461
90296 62428
34733 83769
76626 20346
47219 15731
81322 75681
65022 219
11203 47989
3993 42788
31517 44794
65357 48584
23855 6477
46900 79318
...

output:

633508 633508
96706 80351 69503 41577 27201 50954 38130 48296 34441 63505 30314 38153 42844 97642 2409 8298 57080 85233 84274 66874 30022 17133 87950 66512 11699 82604 3403 64094 39636 16089 76880 22422 70380 58981 49523 86314 16525 56443 95774 1444 78058 52620 57430 65738 5399 29823 63668 74573 934...

result:

points 0.50 jury has the better answer; correct answer = 633508;

Test #70:

score: 25
Acceptable Answer
time: 48ms
memory: 12172kb

input:

93830
5353 89021
42613 10223
62115 81879
34643 18962
76473 5353
4056 4
63378 3164
32851 91689
2518 26936
1309 45627
86974 62153
12093 80379
1172 17485
18649 33293
39255 42562
16938 24457
3653 15693
1541 15201
48606 20698
17492 91689
79239 53179
8731 14575
72896 32618
57110 11569
68213 12567
281 2508...

output:

572628 572628
13335 2301 81280 34359 17228 49001 13037 72268 84795 79601 78648 10166 10909 22361 62463 88998 54813 3016 61924 78047 25804 36746 37656 32031 57533 74593 29219 68864 77893 60393 57684 48589 23305 861 56007 18695 4937 83956 56865 80964 84625 31070 5005 76673 15271 88117 67945 43648 8845...

result:

points 0.50 jury has the better answer; correct answer = 572628;

Test #71:

score: 25
Acceptable Answer
time: 30ms
memory: 10432kb

input:

69696
66494 391
17982 64558
13321 10790
28456 6163
59410 33383
18936 15319
5133 18630
54526 61701
48508 4262
32037 62911
66399 23511
2981 65113
31417 58821
37834 39033
39250 43655
32689 4362
28364 58039
4813 11992
61478 60973
25333 15194
3850 729
12679 60601
50842 19341
3929 42447
45909 17885
16630 ...

output:

431180 431180
24485 58622 11377 55304 41094 4659 34092 57104 11880 39293 15024 34393 19231 552 68149 31411 42455 20605 17467 30446 32017 27062 47194 31879 4133 29320 7955 5439 48048 53344 38313 45574 28590 10358 37442 51622 51343 16276 56118 48275 21694 18669 68416 6916 15631 53167 5343 22051 55856 ...

result:

points 0.50 jury has the better answer; correct answer = 431180;

Test #72:

score: 25
Acceptable Answer
time: 40ms
memory: 10988kb

input:

78987
50446 31217
10794 66216
18480 62852
70322 27242
6686 12303
19970 58804
55986 2835
35829 66681
70335 58144
30611 31562
59624 51532
57846 42319
151 497
27730 1734
74029 34949
70160 65556
18487 56667
38834 11982
32742 69375
31417 28044
33529 21420
68415 51617
5177 2699
65556 72700
27377 78961
600...

output:

480886 480886
14346 63874 31120 10407 29114 50107 42454 25841 20028 17076 3909 8447 27996 75587 70938 31066 27625 74029 10429 76369 1347 59911 74623 51561 4653 11601 17969 72636 8768 60632 13074 40659 50361 33950 14468 17360 44264 36096 64574 54799 71635 34144 30079 8514 21775 25462 23030 34297 3962...

result:

points 0.50 jury has the better answer; correct answer = 480886;

Test #73:

score: 25
Acceptable Answer
time: 47ms
memory: 12652kb

input:

99909
67987 37873
59438 18344
69248 60837
80284 72449
82067 44182
7347 66943
204 99576
20051 93553
16699 42974
50963 131
30206 18503
84146 81416
40002 20626
20959 74043
96265 49617
50869 65018
22501 6623
88439 74277
66330 61579
15157 85873
52321 60174
72666 32099
96871 33612
32525 8346
72291 13831
8...

output:

621708 621708
75424 74816 8862 75262 28822 64598 78028 89969 80172 71179 97131 85245 84483 12550 51181 83734 27229 10056 84522 65752 2433 36450 24736 59712 80888 80081 3318 47920 63987 7803 85814 76247 55468 35947 15882 51778 47176 47300 9655 53418 55204 97116 85796 51608 51140 12680 48253 72869 596...

result:

points 0.50 jury has the better answer; correct answer = 621708;

Test #74:

score: 25
Acceptable Answer
time: 43ms
memory: 12088kb

input:

91413
18433 23117
39518 88780
73634 8375
51086 79039
29685 34503
89810 38630
81368 88746
82927 57444
82104 85400
5906 40542
75577 71148
48623 64005
51512 27586
17173 16511
88746 26255
53758 63629
40899 62791
83800 33391
16089 40303
36362 63446
79889 47281
46465 12939
31493 28594
81159 73849
31493 19...

output:

564658 564658
11493 43230 55709 35111 697 25617 84684 78201 77287 65078 31690 43412 84322 74421 45805 3757 59932 19044 794 21353 37617 59507 77946 50952 48895 22343 30477 56378 47759 45960 89306 18473 78182 35942 83650 51222 80137 28318 69910 8678 63815 70898 4497 35163 56193 73874 29287 81379 2411 ...

result:

points 0.50 jury has the better answer; correct answer = 564658;

Test #75:

score: 25
Acceptable Answer
time: 101ms
memory: 11236kb

input:

100000
19102 79795
15934 47159
11990 20192
16296 51154
97096 27289
4939 91163
2673 42185
1806 13975
48842 10897
26719 19468
26399 9106
1560 63915
52883 66592
18838 46497
39164 1171
67607 11022
96214 28225
96535 32935
4887 10753
27029 87166
96412 97892
2527 4868
35044 4617
1126 96434
65672 48049
2398...

output:

2875752 2875752
78942 28683 40329 23039 62381 49452 25780 95791 24845 56560 59270 30444 72158 98046 12608 40306 50257 91180 64066 30288 30782 85411 7058 81224 11287 14974 34476 90285 26773 59418 50933 78400 46917 60161 64252 78560 2172 4833 26382 79405 84108 42755 36465 45846 24297 91440 80927 78997...

result:

points 0.50 jury has the better answer; correct answer = 2875752;

Test #76:

score: 25
Acceptable Answer
time: 84ms
memory: 11096kb

input:

100000
75186 63877
30682 67959
59008 68830
13637 63860
94404 70388
88997 2416
90186 89995
6381 74173
39644 1479
8990 93543
34924 80311
21555 38157
83335 82822
47379 66027
58545 93415
83098 55197
79276 12395
57124 68551
98957 87628
44742 96005
81802 68017
57385 97315
26358 93734
75229 72243
42347 838...

output:

1934292 1934292
67961 83170 42690 9509 84771 5886 54817 1252 89650 41552 81155 74493 63528 27523 24834 94571 72567 73616 70754 99958 3889 44730 91203 33420 73493 92667 2317 43503 80326 89194 10078 86502 67054 31149 50876 79845 7134 77391 63946 4955 30955 72000 71470 97964 15053 7629 28178 49295 7834...

result:

points 0.50 jury has the better answer; correct answer = 1934292;

Test #77:

score: 25
Acceptable Answer
time: 55ms
memory: 11656kb

input:

93930
41507 82962
74769 3770
72031 54394
13069 62632
45450 83050
13961 63651
15741 74408
23828 24545
49293 25901
74902 68758
34601 8724
91009 12415
25226 79318
21677 57210
35979 45086
14102 12495
72158 47754
51907 35373
90680 67546
53596 88867
42317 11762
9873 67021
866 50185
40981 90832
30093 85377...

output:

977694 977694
18833 49719 23169 11058 22825 83789 34220 83638 37643 30067 22622 39495 34639 56220 57453 73160 20922 75243 47396 29118 10265 32986 7038 19499 33094 261 74382 46630 54073 91609 51569 33262 9132 65386 13408 52536 49971 63675 73678 85496 73363 30706 46520 13389 32409 5662 32326 89380 928...

result:

points 0.50 jury has the better answer; correct answer = 977694;

Test #78:

score: 25
Acceptable Answer
time: 35ms
memory: 9192kb

input:

66666
2708 28938
18111 55593
46507 60492
28211 60354
62177 42106
32334 46682
54891 60720
12631 32446
33964 14077
33843 53751
10493 48939
48573 15925
47187 42344
42818 14380
28170 62539
63144 21807
46841 4470
27694 45562
3165 43146
3215 65473
7421 63611
32774 63019
61958 43387
40532 31463
21685 53001...

output:

798958 798958
35718 44425 10258 24063 20822 61367 13010 59178 22000 63669 351 11415 60237 45921 53824 710 61842 30761 117 48692 35068 26931 65002 65795 7411 53150 9614 5178 16961 53353 29251 50133 10465 42174 55893 45363 1619 649 47940 54266 27794 21832 46918 58850 60694 33401 9447 10800 4436 29344 ...

result:

points 0.50 jury has the better answer; correct answer = 798958;

Test #79:

score: 25
Acceptable Answer
time: 45ms
memory: 9856kb

input:

77777
49369 24449
54325 6946
35965 66783
76466 71203
2951 49141
58917 10371
2247 50627
17325 45488
64322 10832
54119 16739
71942 22004
5669 59682
30435 46823
75426 8464
49716 45345
11249 63092
53811 30685
50209 59714
981 22555
24635 3770
12609 18627
59905 51515
5014 30189
54811 7392
69500 39567
6452...

output:

887574 887574
45511 39258 2204 57167 75347 31307 61233 75324 30118 49192 32858 31792 49734 67731 63052 29440 75694 64667 27332 3002 46913 21296 17658 49077 38572 40246 41407 22795 17361 31852 63232 13587 54731 13423 69476 21698 25863 52107 67623 7859 8997 9076 4880 4790 52959 13393 40213 977 55828 6...

result:

points 0.50 jury has the better answer; correct answer = 887574;

Test #80:

score: 25
Acceptable Answer
time: 114ms
memory: 11316kb

input:

99999
34134 31512
55415 48626
9899 98702
24742 36230
68336 49341
47014 26483
8014 23654
80819 6762
4106 2043
53126 95878
40268 15773
38569 82908
17144 593
61589 33340
21595 14286
2307 46262
13520 33753
97081 21121
64483 80578
37007 75704
27327 32104
79431 38166
75683 39406
13333 86195
52529 60493
45...

output:

2875718 2875718
40256 52830 85508 57885 15751 50661 68434 40128 97165 73749 18191 5430 97565 82404 62977 77716 35878 50137 26449 95434 15332 77176 79761 79075 37386 10405 73818 85203 18889 91524 64862 75931 47705 44932 8121 85985 63693 73591 90630 35609 41441 1055 57393 15290 78877 60556 79952 28580...

result:

points 0.50 jury has the better answer; correct answer = 2875718;

Test #81:

score: 25
Acceptable Answer
time: 44ms
memory: 11508kb

input:

93792
74714 28726
23910 20740
3508 41621
37903 76011
72483 64428
16621 2707
26752 16310
4099 66364
69520 23944
68543 26259
70570 38828
3615 51139
42643 6953
44734 75053
17579 54545
47875 81814
78574 49423
20229 3741
70837 3534
59233 83851
92737 92812
1120 57640
15001 8970
35263 51813
86949 62582
143...

output:

749346 749346
19936 52262 70591 12676 42462 46169 35502 32945 11284 2702 34664 19043 22722 39397 36520 8623 15113 61120 5487 20263 34669 14640 57587 22492 58330 55372 3822 30529 12383 58709 31027 74105 70292 69732 62195 58665 1911 61002 57307 30668 39521 33657 82633 7858 34565 75165 71770 40061 4679...

result:

points 0.50 jury has the better answer; correct answer = 749346;

Test #82:

score: 25
Acceptable Answer
time: 45ms
memory: 12336kb

input:

99123
2797 6945
30658 68802
61712 84113
62236 90495
7451 10575
503 52469
18199 28556
34303 50085
3793 18450
79309 37327
76471 2366
60651 15777
86221 75493
93198 91391
76798 43771
12482 60504
31236 53949
87601 70233
287 95910
96819 3931
17535 8267
55279 45400
43114 41790
79370 12949
39345 23475
47591...

output:

563982 563982
70639 9457 69542 88680 2360 30257 30864 90936 9838 21808 89923 79486 24851 31511 63502 94543 81245 15913 32405 14995 14297 20700 32117 22697 4733 22817 3494 11062 81609 57245 8952 72689 17689 82275 4335 94004 73164 76201 15287 1439 69310 7656 57146 72780 43248 96321 1522 14640 22357 84...

result:

points 0.50 jury has the better answer; correct answer = 563982;
English 繁體中文 简体中文

Server Time: 2024-12-02 17:40:29 | OpenSource Project