QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#292790#5706. Villagewhdywjd56 87ms170632kbC++145.7kb2023-12-28 13:24:102023-12-28 13:24:11

Judging History

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

  • [2023-12-28 13:24:11]
  • 评测
  • 测评结果：56
  • 用时：87ms
  • 内存：170632kb
查看
  • [2023-12-28 13:24:10]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define ll long long
#define lf double
#define _1 first
#define _2 second
#define _mp make_pair
#define _pb push_back
#define MAX_N 222222
#define inf 2222222222222222222ll

using namespace std;

ll read(){ll x = 0;char c = 0, v = 0;do{c = getchar();if(c == '-')v = 1;} while(c < '0' || c > '9');do{x = (x << 3) + (x << 1) + c - '0';c = getchar();} while(c >= '0' && c <= '9');return v ? -x : x;}

template<size_t N>
struct Tree
{
    int rt;
    vector<int> G[N];
    void build(int x, int y)
    {
        G[x]._pb(y);
        G[y]._pb(x);
        //n = max(n, max(x, y));
    }

    #define Edgs(p, x, f) for(auto p: G[x]) if(p != (f))
    int SIZE, MNVAL, MNPOS;
    void Gdfs1(int x, int f)
    {
        SIZE++;
        Edgs(p, x, f)
            Gdfs1(p, x);
    }

    int Gdfs2(int x, int f)
    {
        int sz = 1, mxsz = 0;
        Edgs(p, x, f)
        {
            int d = Gdfs2(p, x);
            sz += d;
            mxsz = max(mxsz, d);
        }
        mxsz = max(mxsz, SIZE - sz);
        if(mxsz < MNVAL)
            MNVAL = mxsz, MNPOS = x;
        return sz;
    }

    int Gx()
    {
        SIZE = 0, MNVAL = N, MNPOS = 0;
        Gdfs1(1, 0), Gdfs2(1, 0);
        return MNPOS;
    }

    int sz[N];
    void dfs1(int x, int f)
    {
        sz[x] = 1;
        Edgs(p, x, f)
        {
            dfs1(p, x);
            sz[x] += sz[p];
        }
    }

    ll dp[N][2];
    int mat1[N];
    ll ans1;
    void dfs2(int x, int f)
    {
        if(sz[x] == 1)
        {
            dp[x][0] = -2 * (int)N;
            dp[x][1] = 0;
            return;
        }
        dp[x][0] = 1, dp[x][1] = 0;
        bool flag = 0;
        Edgs(p, x, f)
        {
            dfs2(p, x);
            dp[x][1] += max(dp[p][0], dp[p][1]);
            if(dp[p][0] > dp[p][1])
                dp[x][0] += dp[p][0];
            else
                flag = 1, dp[x][0] += dp[p][1];
        }
        if(flag)
            return;
        ll mn = N;
        Edgs(p, x, f)
            mn = min(mn, dp[p][0] - dp[p][1]);
        dp[x][0] -= mn;
    }

    int output1(int x, int f, bool sta)
    {
        //printf(" %d %d\n", x, (int)sta);
        if(sz[x] == 1)
            return x;
        if(sta)
        {
            int lst = x;
            Edgs(p, x, f)
                if(dp[p][0] >= dp[p][1])
                    output1(p, x, 0);
                else
                {
                    mat1[lst] = output1(p, x, 1);
                    lst = mat1[lst];
                }
            return lst;
        }
        bool flag = 0;
        Edgs(p, x, f)
            if(dp[p][0] <= dp[p][1])
                flag = 1;
        if(flag)
        {
            ll lst = x;
            Edgs(p, x, f)
            {
                if(dp[p][0] > dp[p][1])
                    output1(p, x, 0);
                else
                {
                    mat1[lst] = output1(p, x, 1);
                    lst = mat1[lst];
                }
            }
            mat1[lst] = x;
            return 0;
        }
        ll mn = N;
        int mnp = 0;
        Edgs(p, x, f)
            if(dp[p][0] - dp[p][1] < mn)
                mn = dp[p][0] - dp[p][1], mnp = p;
        Edgs(p, x, f)
        {
            if(p == mnp)
            {
                mat1[x] = output1(p, x, 1);
                mat1[mat1[x]] = x;
            }
            else
                output1(p, x, 0);
        }
        return 0;
    }

    int m;
    stack<int> nds[N];
    priority_queue<pair<int, int> > q; // <size, id>
    int mat2[N];
    ll ans2;
    void dfs3(int x, int f, int d, int id)
    {
        nds[id].push(x);
        ans2 += 2 * d;
        Edgs(p, x, f)
            dfs3(p, x, d + 1, id);
    }

    void main(int n)
    {
        rt = Gx();
        //printf("%d\n", rt);
        dfs1(rt, 0);
        dfs2(rt, 0);
        ans1 = 2 * (n - dp[rt][0]);
        output1(rt, 0, 0);
        //return;
        m = ans2 = 0;
        Edgs(p, rt, 0)
        {
            m++;
            dfs3(p, rt, 1, m);
            q.push(_mp(sz[p], m));
        }
        //return;
        for(int i = 1; 2 * i < n; i++)
        {
            pair<int, int> p1 = q.top();
            q.pop();
            pair<int, int> p2 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            int x2 = nds[p2._2].top();
            nds[p2._2].pop();
            if(i == 1 && (n & 1))
                mat2[x1] = rt, mat2[rt] = x2, mat2[x2] = x1;
            else
                mat2[x1] = x2, mat2[x2] = x1;
            if(p1._1 > 1)
                q.push(_mp(p1._1 - 1, p1._2));
            if(p2._1 > 1)
                q.push(_mp(p2._1 - 1, p2._2));
        }
        //return;
        if(!(n & 1))
        {
            pair<int, int> p1 = q.top();
            q.pop();
            int x1 = nds[p1._2].top();
            nds[p1._2].pop();
            mat2[x1] = rt;
            mat2[rt] = x1;
        }
    }
};

Tree<MAX_N> tr;
int n;

void MAIN()
{
    n = read();
    for(int i = 1; i < n; i++)
        tr.build(read(), read());
    tr.main(n);
    printf("%lld %lld\n", tr.ans1, tr.ans2);
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat1[i]);
    printf("\n");
    for(int i = 1; i <= n; i++)
        printf("%d ", tr.mat2[i]);
    printf("\n");
}

void CLEAR()
{
    ;
}

void EXP()
{
    ;
}

int main()
{
    EXP();
    int T = 1;
    while(T--)
        MAIN(), CLEAR();
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 28ms
memory: 161464kb

input:

4
1 2
2 3
3 4

output:

4 8
2 1 4 3 
4 3 2 1

result:

points 1.0 correct answer = 4; correct answer = 8;

Test #2:

score: 12
Accepted
time: 19ms
memory: 161420kb

input:

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

output:

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

result:

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

Test #3:

score: 12
Accepted
time: 19ms
memory: 161424kb

input:

2
1 2

output:

2 2
2 1 
2 1

result:

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

Test #4:

score: 12
Accepted
time: 39ms
memory: 161632kb

input:

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

output:

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

result:

points 1.0 correct answer = 8; correct answer = 20;

Test #5:

score: 12
Accepted
time: 23ms
memory: 161692kb

input:

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

output:

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

result:

points 1.0 correct answer = 8; correct answer = 24;

Test #6:

score: 12
Accepted
time: 24ms
memory: 161424kb

input:

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

output:

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

result:

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

Test #7:

score: 12
Accepted
time: 19ms
memory: 161420kb

input:

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

output:

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

result:

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

Test #8:

score: 12
Accepted
time: 23ms
memory: 161480kb

input:

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

output:

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

result:

points 1.0 correct answer = 10; correct answer = 22;

Test #9:

score: 12
Accepted
time: 20ms
memory: 161508kb

input:

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

output:

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

result:

points 1.0 correct answer = 14; correct answer = 22;

Test #10:

score: 12
Accepted
time: 23ms
memory: 164508kb

input:

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

output:

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

result:

points 1.0 correct answer = 10; correct answer = 30;

Test #11:

score: 12
Accepted
time: 16ms
memory: 161432kb

input:

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

output:

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

result:

points 1.0 correct answer = 10; correct answer = 50;

Test #12:

score: 12
Accepted
time: 24ms
memory: 164236kb

input:

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

output:

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

result:

points 1.0 correct answer = 10; correct answer = 42;

Test #13:

score: 12
Accepted
time: 31ms
memory: 161476kb

input:

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

output:

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

result:

points 1.0 correct answer = 14; correct answer = 28;

Test #14:

score: 12
Accepted
time: 20ms
memory: 164344kb

input:

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

output:

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

result:

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

Test #15:

score: 12
Accepted
time: 19ms
memory: 161648kb

input:

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

output:

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

result:

points 1.0 correct answer = 14; correct answer = 28;

Test #16:

score: 12
Accepted
time: 21ms
memory: 164276kb

input:

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

output:

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

result:

points 1.0 correct answer = 16; correct answer = 22;

Test #17:

score: 12
Accepted
time: 16ms
memory: 164112kb

input:

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

output:

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

result:

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

Subtask #2:

score: 19
Acceptable Answer

Dependency #1:

100%
Accepted

Test #18:

score: 38
Accepted
time: 24ms
memory: 161416kb

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:

316 2186
131 44 58 97 209 130 24 249 230 179 89 214 106 74 182 255 237 63 207 35 175 68 55 7 87 75 70 147 100 159 83 150 98 54 20 112 152 48 145 43 78 154 136 2 125 180 123 79 233 221 222 18 213 34 224 71 51 3 178 169 129 95 52 173 4 81 229 22 84 27 56 116 200 14 165 23 203 46 38 39 251 66 31 168 18...

result:

points 1.0 correct answer = 316; correct answer = 2186;

Test #19:

score: 38
Accepted
time: 25ms
memory: 163872kb

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:

636 5114
186 331 73 415 410 399 474 187 321 51 109 491 477 4 228 482 29 23 15 87 466 16 253 211 34 341 188 163 233 425 498 329 336 447 487 442 153 10 481 44 134 154 164 40 159 368 264 127 490 279 38 184 378 106 437 492 303 48 22 473 226 273 192 28 262 340 349 428 414 395 429 110 3 307 25 205 267 391...

result:

points 1.0 correct answer = 636; correct answer = 5114;

Test #20:

score: 38
Accepted
time: 15ms
memory: 161504kb

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:

614 4106
23 121 215 242 68 436 386 312 466 120 356 324 51 149 495 357 143 10 321 427 479 296 239 282 477 492 481 417 165 319 364 216 434 35 164 115 409 332 444 318 185 236 29 73 225 270 424 275 159 307 13 378 352 248 430 8 119 314 469 438 12 217 145 453 175 350 133 308 287 299 118 435 473 276 410 29...

result:

points 1.0 correct answer = 614; correct answer = 4106;

Test #21:

score: 38
Accepted
time: 11ms
memory: 164024kb

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:

1294 14376
255 599 95 408 257 846 941 792 725 703 741 972 391 547 940 239 392 756 541 731 238 891 299 306 121 608 931 9 818 717 457 605 103 274 621 949 830 691 961 742 979 933 310 263 357 797 494 905 169 745 234 874 982 303 912 718 288 716 748 988 122 591 368 667 28 623 157 854 23 269 61 261 795 409...

result:

points 1.0 correct answer = 1294; correct answer = 14376;

Test #22:

score: 38
Accepted
time: 19ms
memory: 161484kb

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:

1244 11674
810 616 295 861 537 475 187 491 464 404 308 45 931 681 652 581 49 937 835 212 839 963 73 560 359 129 166 26 105 617 831 860 987 67 326 81 591 112 347 385 678 503 59 465 650 282 715 99 17 535 189 653 568 448 171 598 525 748 530 367 722 490 646 343 397 587 277 840 236 637 113 145 898 792 19...

result:

points 1.0 correct answer = 1244; correct answer = 11674;

Test #23:

score: 38
Accepted
time: 28ms
memory: 164176kb

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:

1266 11812
918 668 729 527 514 739 865 785 609 717 309 790 518 920 401 248 241 707 427 303 271 933 371 93 372 780 378 457 885 393 48 910 575 110 190 852 91 363 208 764 562 387 636 695 721 675 447 31 365 366 743 420 540 334 54 344 191 864 467 312 619 900 840 907 684 746 698 593 415 314 551 408 660 80...

result:

points 1.0 correct answer = 1266; correct answer = 11812;

Test #24:

score: 38
Accepted
time: 23ms
memory: 161756kb

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:

1000 500000
902 350 486 860 69 680 799 576 730 482 842 850 604 615 654 376 721 763 736 64 635 873 999 555 252 195 73 510 464 737 502 272 397 740 281 420 99 798 752 220 196 558 63 198 977 934 267 245 126 832 452 590 472 302 529 720 65 969 505 657 714 864 43 20 57 207 578 153 5 425 219 710 27 375 349 ...

result:

points 1.0 correct answer = 1000; correct answer = 500000;

Test #25:

score: 38
Accepted
time: 19ms
memory: 163708kb

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:

1140 91036
729 711 453 310 147 12 120 207 115 750 648 6 247 36 355 840 114 618 287 650 419 949 89 122 31 836 53 464 733 510 25 217 880 712 713 14 110 673 564 49 628 709 717 326 255 119 686 455 40 700 937 789 27 68 366 747 866 911 285 676 771 282 304 748 788 636 702 309 753 2 663 425 801 265 154 174 ...

result:

points 1.0 correct answer = 1140; correct answer = 91036;

Test #26:

score: 38
Accepted
time: 27ms
memory: 161444kb

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:

1028 43956
64 732 571 357 22 754 803 474 507 21 237 404 23 405 894 547 369 477 99 810 10 39 13 213 552 899 117 819 111 792 847 391 469 558 716 291 875 242 5 639 155 65 533 130 565 255 864 779 172 78 87 176 90 719 371 904 723 842 109 586 244 348 679 1 42 292 752 817 742 68 897 688 695 245 485 856 542...

result:

points 1.0 correct answer = 1028; correct answer = 43956;

Test #27:

score: 38
Accepted
time: 15ms
memory: 163996kb

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:

1002 250998
407 494 686 447 924 434 742 709 673 456 414 160 780 488 858 30 790 552 214 972 599 663 508 946 642 351 973 448 585 16 423 564 671 813 699 374 674 574 679 728 812 806 364 958 710 566 388 939 947 967 286 694 138 834 320 724 820 375 201 178 983 166 123 637 963 587 586 862 518 228 669 936 93...

result:

points 1.0 correct answer = 1002; correct answer = 250998;

Test #28:

score: 38
Accepted
time: 28ms
memory: 161712kb

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:

1248 127496
521 650 219 129 600 128 507 427 836 147 344 919 511 112 624 21 980 323 756 563 872 612 107 145 609 608 996 676 182 834 965 377 983 333 773 958 720 699 833 790 221 725 236 979 628 206 297 273 84 467 74 812 227 411 134 466 636 10 522 499 691 366 215 590 299 170 937 39 690 220 454 633 245 3...

result:

points 1.0 correct answer = 1248; correct answer = 127496;

Test #29:

score: 38
Accepted
time: 33ms
memory: 164272kb

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 403 330 186 145 899 987 676 157 686 473 632 941 60 959 845 759 315 291 947 1 650 809 689 885 214 95 55 136 225 278 872 348 661 220 43 709 662 478 170 735 240 456 395 699 613 211 321 944 755 867 449 882 744 612 175 758 910 242 408 847 270 811 203 250 869 955 659 746 40 447 5...

result:

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

Test #30:

score: 38
Accepted
time: 15ms
memory: 161472kb

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:

1974 2962
408 36 116 675 167 413 516 411 852 473 635 805 625 109 803 74 442 35 544 874 81 491 75 506 227 474 141 727 11 228 499 371 25 743 584 293 511 348 651 637 171 249 245 257 4 659 338 9 753 321 577 203 863 677 160 657 705 68 858 415 145 595 725 222 185 783 22 855 78 97 50 96 886 702 6 488 883 2...

result:

points 1.0 correct answer = 1974; correct answer = 2962;

Test #31:

score: 38
Accepted
time: 15ms
memory: 161476kb

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:

1940 7958
907 997 33 109 574 120 899 889 195 282 803 423 605 87 603 51 314 659 302 142 831 633 259 108 275 52 405 303 669 914 826 564 7 373 485 676 293 821 23 377 214 122 441 189 157 490 662 141 756 843 666 238 233 187 96 209 643 445 393 591 528 647 678 597 558 248 291 950 757 151 739 935 69 646 607...

result:

points 1.0 correct answer = 1940; correct answer = 7958;

Test #32:

score: 38
Accepted
time: 20ms
memory: 161548kb

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:

1756 4288
344 713 707 696 466 529 5 569 678 27 346 141 396 147 96 745 512 36 476 144 164 876 375 533 419 219 355 814 221 727 431 519 866 254 665 782 192 110 759 390 778 503 230 252 117 560 886 340 495 402 772 531 86 689 464 885 693 762 271 190 737 265 35 289 328 486 418 25 202 406 881 347 237 44 294...

result:

points 1.0 correct answer = 1756; correct answer = 4288;

Test #33:

score: 38
Accepted
time: 24ms
memory: 161588kb

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:

1392 9628
746 701 523 226 856 669 975 242 996 664 416 985 49 767 451 653 670 433 71 272 208 17 994 823 278 945 881 615 941 695 671 719 918 870 314 525 816 588 134 340 67 385 713 393 940 770 837 595 894 789 726 293 302 33 909 802 70 716 155 434 205 532 247 993 986 874 920 338 790 310 292 300 351 818 ...

result:

points 1.0 correct answer = 1392; correct answer = 9628;

Test #34:

score: 38
Accepted
time: 16ms
memory: 161548kb

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:

1782 6554
193 758 766 717 30 815 678 803 983 335 472 870 729 185 957 10 871 771 187 964 503 235 907 689 431 380 147 691 163 583 707 642 972 790 593 63 612 601 535 664 392 728 125 348 319 219 475 845 921 308 177 59 331 617 526 522 985 699 374 580 916 451 16 385 877 785 913 675 796 131 209 946 669 462...

result:

points 1.0 correct answer = 1782; correct answer = 6554;

Test #35:

score: 38
Accepted
time: 23ms
memory: 161504kb

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:

1874 5278
682 876 537 723 857 926 134 588 41 153 435 104 667 256 465 372 313 915 676 619 959 804 274 751 841 339 151 875 660 707 284 326 352 831 218 290 581 169 349 962 457 569 142 910 694 645 920 388 361 439 392 324 526 320 67 97 900 419 199 466 70 483 26 579 922 341 484 132 923 774 609 210 442 927...

result:

points 1.0 correct answer = 1874; correct answer = 5278;

Test #36:

score: 38
Accepted
time: 32ms
memory: 161480kb

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:

1980 3906
470 850 171 46 231 351 113 456 947 996 328 911 823 531 398 69 768 751 238 128 785 25 690 841 710 523 50 528 907 63 846 336 640 501 240 611 118 575 738 307 649 592 701 498 713 94 59 579 561 633 199 617 147 628 990 58 594 786 536 21 769 359 362 298 412 820 394 867 916 440 476 644 215 647 979...

result:

points 1.0 correct answer = 1980; correct answer = 3906;

Test #37:

score: 38
Accepted
time: 15ms
memory: 161716kb

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:

1890 6546
510 390 240 849 994 712 453 770 763 201 251 518 535 638 947 233 198 950 758 853 432 134 395 833 911 501 92 422 403 168 22 78 262 684 5 204 389 640 613 755 818 884 225 618 493 866 89 177 979 221 683 16 623 414 29 462 137 576 999 943 815 163 220 123 918 469 87 926 821 699 521 685 735 203 189...

result:

points 1.0 correct answer = 1890; correct answer = 6546;

Test #38:

score: 38
Accepted
time: 12ms
memory: 161716kb

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:

1938 4626
222 30 263 667 899 630 512 399 765 806 997 719 752 506 774 169 932 791 496 367 112 356 685 119 535 319 767 99 82 738 646 102 962 756 313 737 761 989 152 816 406 89 759 255 996 888 723 477 787 139 784 987 333 986 493 272 231 539 559 188 913 788 705 852 802 840 296 365 438 459 77 458 978 844...

result:

points 1.0 correct answer = 1938; correct answer = 4626;

Test #39:

score: 38
Accepted
time: 27ms
memory: 161480kb

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:

1938 4914
186 886 896 460 363 573 410 906 292 744 535 541 544 953 124 647 536 518 425 281 607 644 374 93 132 835 382 244 558 770 929 385 175 805 614 704 191 77 625 115 786 379 101 501 190 912 522 737 839 913 597 17 435 378 439 571 183 105 464 695 910 452 529 678 925 92 767 13 673 497 578 394 766 655...

result:

points 1.0 correct answer = 1938; correct answer = 4914;

Test #40:

score: 38
Accepted
time: 19ms
memory: 161732kb

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:

1066 7882
737 171 788 353 587 509 218 409 153 335 344 103 648 503 305 376 364 649 858 271 704 405 538 774 349 373 415 740 346 70 520 529 849 65 677 635 549 666 53 697 887 745 235 359 591 184 293 545 809 513 896 263 39 539 417 734 150 327 818 167 496 610 669 495 34 892 253 200 483 31 442 484 374 873 ...

result:

points 1.0 correct answer = 1066; correct answer = 7882;

Test #41:

score: 19
Acceptable Answer
time: 26ms
memory: 161448kb

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:

1144 10654
19 769 366 272 51 547 388 473 424 27 227 258 648 67 868 129 231 292 525 764 597 164 327 10 242 430 142 558 78 593 620 130 117 421 311 888 678 806 382 94 649 74 205 466 521 57 680 636 107 665 805 887 808 393 463 737 54 809 834 686 879 245 147 510 420 831 14 559 585 16 733 264 501 42 316 76...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 10654;

Test #42:

score: 19
Acceptable Answer
time: 23ms
memory: 163936kb

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:

682 7190
392 212 321 491 386 308 280 6 194 490 226 310 42 78 318 378 210 353 372 437 496 132 412 255 44 82 358 104 247 458 211 475 448 106 504 441 261 118 135 424 362 495 69 110 385 478 9 328 268 173 320 393 18 50 434 470 87 336 348 236 242 224 422 418 326 192 413 176 43 31 329 324 296 183 259 134 2...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 7190;

Test #43:

score: 19
Acceptable Answer
time: 23ms
memory: 161456kb

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:

1330 15930
183 274 481 242 53 89 203 293 712 929 143 857 983 129 198 254 260 478 185 897 72 392 664 733 340 201 326 525 687 114 331 310 107 169 128 62 719 27 830 639 122 782 637 623 794 329 1 869 590 307 291 991 465 109 447 158 58 923 587 41 280 561 859 563 117 52 419 564 251 633 179 409 15 71 884 5...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 15930;

Test #44:

score: 38
Accepted
time: 23ms
memory: 161520kb

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:

684 7206
228 159 189 182 322 198 511 121 178 28 486 164 397 165 256 161 345 134 40 450 16 471 366 201 29 315 185 289 247 321 186 62 236 37 465 227 127 294 503 502 129 117 133 163 94 504 473 89 52 300 91 361 282 413 379 312 206 218 2 234 391 166 144 72 126 80 68 86 221 139 461 343 490 224 188 74 467 ...

result:

points 1.0 correct answer = 684; correct answer = 7206;

Test #45:

score: 38
Accepted
time: 23ms
memory: 163984kb

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:

1596 9094
730 328 811 311 356 314 927 250 929 599 144 282 267 914 44 636 270 438 809 581 349 279 753 197 292 1 2 336 41 396 572 792 104 339 214 965 428 979 469 964 439 146 721 414 909 954 318 457 182 308 635 805 49 391 991 437 198 8 640 240 604 257 68 162 802 620 160 408 862 24 736 157 375 990 577 6...

result:

points 1.0 correct answer = 1596; correct answer = 9094;

Test #46:

score: 38
Accepted
time: 29ms
memory: 161812kb

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:

1814 5748
851 227 62 391 318 868 44 233 160 590 183 530 758 188 63 151 108 752 295 346 606 298 96 70 223 51 413 315 363 675 105 939 501 135 810 978 700 309 616 59 762 154 303 664 220 257 783 747 819 345 965 593 424 293 287 677 168 980 959 678 894 513 115 976 811 755 150 660 209 185 206 607 267 800 7...

result:

points 1.0 correct answer = 1814; correct answer = 5748;

Test #47:

score: 38
Accepted
time: 25ms
memory: 161472kb

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:

1980 3794
847 920 747 78 667 527 577 178 516 426 693 908 947 930 973 913 403 952 723 55 781 56 445 709 42 199 761 21 69 263 922 875 480 869 102 514 897 157 934 66 871 475 350 650 406 261 437 524 549 314 812 868 498 539 619 181 518 320 658 867 248 755 358 448 796 274 218 22 376 377 569 112 340 718 19...

result:

points 1.0 correct answer = 1980; correct answer = 3794;

Subtask #3:

score: 25
Acceptable Answer

Dependency #1:

100%
Accepted

Dependency #2:

50%
Acceptable Answer

Test #48:

score: 50
Accepted
time: 72ms
memory: 167260kb

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:

111632 1514350
41502 74527 64675 17581 1061 73123 26445 35831 18757 81500 8159 35821 57733 41064 23891 542 44897 19955 31471 84394 62804 49756 64465 32369 39347 50665 32642 32283 13379 76143 211 33934 59751 65818 26185 18902 86524 3813 57513 48947 31029 7491 57727 88248 53951 68728 47594 42451 63099...

result:

points 1.0 correct answer = 111632; correct answer = 1514350;

Test #49:

score: 50
Accepted
time: 80ms
memory: 167560kb

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:

128320 2159862
52903 19776 79437 50136 87240 41873 62741 75685 79227 19609 50280 7447 26911 28055 98100 19726 84050 12278 97404 83063 92119 90722 99619 98165 66526 89445 9956 19338 1116 21389 28065 73598 88787 30733 89066 6216 56434 4717 618 23670 44136 20373 28457 81802 40077 57444 31005 76358 9212...

result:

points 1.0 correct answer = 128320; correct answer = 2159862;

Test #50:

score: 50
Accepted
time: 76ms
memory: 168048kb

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:

123860 1952940
29587 93427 57549 48964 62464 58996 8038 83230 71860 60179 57222 41095 84759 14246 18660 65558 68573 74198 38263 65212 66237 79664 29395 98711 41109 48096 68414 1433 76381 10231 55422 97108 97381 81932 53765 8820 10128 49258 55200 58993 49612 11805 41661 41108 44045 80257 19286 76015 ...

result:

points 1.0 correct answer = 123860; correct answer = 1952940;

Test #51:

score: 50
Accepted
time: 68ms
memory: 164700kb

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:

99504 1605682
34226 75028 56968 19310 6760 56789 15714 12837 31395 22604 22504 34975 36782 64388 1417 22051 26238 317 22066 39036 15068 10393 59411 1065 58836 34420 24133 2107 60306 25228 51232 72861 15799 29998 4092 1849 15141 64945 54398 61392 51093 40268 31576 66097 32280 17547 10023 16853 53057 ...

result:

points 1.0 correct answer = 99504; correct answer = 1605682;

Test #52:

score: 50
Accepted
time: 79ms
memory: 167628kb

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:

121438 1740764
40273 18262 86267 22607 19920 63219 24926 92411 41753 1091 56496 76445 91790 26481 2436 57009 77559 18516 94297 38031 96328 92711 92295 31819 8851 98322 60410 46017 83392 2223 51207 72406 72318 93694 90691 13247 59222 12976 5848 63085 72589 22585 28615 33979 80125 19448 45777 69304 96...

result:

points 1.0 correct answer = 121438; correct answer = 1740764;

Test #53:

score: 50
Accepted
time: 63ms
memory: 167148kb

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:

113806 1835832
28048 46462 48816 46565 27949 44060 10789 66975 48147 31794 8965 33932 18168 74165 29721 2223 54717 64674 41640 7588 7336 18028 50967 51276 70321 21641 60578 42782 465 13161 35400 32644 34275 49972 31811 2900 20177 80930 65817 64779 29134 3455 27774 41262 80024 7349 41093 32449 72996 ...

result:

points 1.0 correct answer = 113806; correct answer = 1835832;

Test #54:

score: 50
Accepted
time: 55ms
memory: 166872kb

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:

50000 1250000000
17058 6776 22005 23828 45874 39303 4476 14335 28363 17962 6383 14168 43413 43700 10945 12093 27445 35138 36634 29055 36476 44004 38418 37079 36303 22322 20233 38966 16768 25054 19677 231 19517 10469 34913 47267 40033 5554 3908 8808 19679 39204 4293 14118 24876 35880 17358 32695 7872...

result:

points 1.0 correct answer = 50000; correct answer = 1250000000;

Test #55:

score: 50
Accepted
time: 83ms
memory: 170632kb

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:

100000 5000000000
16429 71778 52159 64739 78956 71205 90635 51220 84989 35155 65772 28847 35720 49758 81397 65734 91368 54768 98851 66373 103 30647 70581 65203 70270 69907 72714 79091 77499 70250 46984 55913 75404 44636 94542 71876 76988 49377 52894 80912 61976 15699 67811 27186 81576 87503 92977 56...

result:

points 1.0 correct answer = 100000; correct answer = 5000000000;

Test #56:

score: 50
Accepted
time: 79ms
memory: 169044kb

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:

110618 2504160170
84815 1128 61528 30386 41409 65941 65666 36412 21566 831 26535 37396 68895 26628 75911 84885 95744 89159 66197 17892 86419 13776 19151 48193 7963 13598 67754 6049 88218 22948 43632 58253 83016 55157 9311 6589 69523 894 56639 72349 5190 33216 44062 5388 66307 70820 30067 34390 24790...

result:

points 1.0 correct answer = 110618; correct answer = 2504160170;

Test #57:

score: 50
Accepted
time: 87ms
memory: 168484kb

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:

110634 1634005140
69272 39075 21524 68497 84436 52213 88637 33512 93355 26197 85399 45718 81695 89756 95811 15715 79365 82938 42491 36939 97235 80198 10125 90675 47600 40941 91600 95902 60933 59598 5037 59956 82476 14287 36041 80772 45699 40701 58050 44889 65 15215 84249 70831 14789 31288 76352 2119...

result:

points 1.0 correct answer = 110634; correct answer = 1634005140;

Test #58:

score: 50
Accepted
time: 75ms
memory: 168264kb

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:

112768 830383780
12719 90340 6638 65886 23745 32853 53812 31292 16139 82349 5555 6238 22816 37451 88934 25125 67703 5794 95978 31649 10143 58521 37858 21268 13255 61336 96542 71917 12622 21483 33069 81334 4461 48580 76954 82827 75776 78335 1657 67379 4907 94611 6790 19235 81613 68894 42671 54357 506...

result:

points 1.0 correct answer = 112768; correct answer = 830383780;

Test #59:

score: 50
Accepted
time: 75ms
memory: 167904kb

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:

132516 81728820
56946 30086 71220 75741 79924 31247 5514 38481 49014 79779 26964 77213 5908 78778 12487 78003 53155 90462 89461 9779 97379 14731 71830 77263 11861 9260 62056 30228 80815 45031 27920 68815 70962 7011 2863 9892 974 12212 92541 9340 44641 99431 35248 45915 16360 46925 19760 3871 42563 2...

result:

points 1.0 correct answer = 132516; correct answer = 81728820;

Test #60:

score: 50
Accepted
time: 68ms
memory: 167576kb

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
56723 58034 6015 59138 11468 81181 23942 65908 12360 69217 7319 65283 59235 70831 10143 20949 3523 34544 41809 38946 69665 51478 53710 3710 61274 82759 90836 88093 83513 84255 22820 642 45095 92138 64889 11209 92533 66661 92691 69460 29022 57350 47441 86007 81456 50514 59757 15192 4680...

result:

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

Test #61:

score: 50
Accepted
time: 70ms
memory: 167468kb

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:

199990 359886
49812 65583 73274 77101 10945 16460 41672 6623 78568 81371 69844 71401 14302 96917 32113 55355 93694 13694 97121 48386 64223 35983 97003 81205 35814 97997 94064 46393 85335 77811 33320 71563 22493 54292 79989 48043 85819 20918 23673 70387 88596 27160 58690 13845 79932 73145 34922 89933...

result:

points 1.0 correct answer = 199990; correct answer = 359886;

Test #62:

score: 50
Accepted
time: 65ms
memory: 167916kb

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:

199800 932808
71997 7605 48666 19670 69752 2312 18718 62210 92413 97763 7768 8412 55533 84798 20473 68389 70331 52113 99671 20563 81394 88369 68822 20401 49932 9827 2213 96078 62958 60065 18429 6703 26963 80585 9966 77210 74885 96011 8759 28745 55298 94211 87832 70432 44400 8137 47448 91354 98239 95...

result:

points 1.0 correct answer = 199800; correct answer = 932808;

Test #63:

score: 50
Accepted
time: 51ms
memory: 167680kb

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:

187472 837534
34224 59127 50562 37009 53297 17853 11369 60920 85087 67586 60203 13255 15571 69314 41483 73914 35070 80672 72584 15736 23743 72572 50432 61817 8578 57127 39633 49196 25688 62045 91287 38518 72687 39194 14834 71863 29155 19716 23403 58722 46324 25504 79847 57764 63809 86267 35077 81402...

result:

points 1.0 correct answer = 187472; correct answer = 837534;

Test #64:

score: 50
Accepted
time: 59ms
memory: 167916kb

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:

181934 1209576
91817 95205 38840 21821 42059 69798 26508 2811 27566 37683 11884 78678 16611 73343 44999 46807 20806 67722 42998 5362 92032 94940 12021 94062 31279 33086 58557 88610 36635 9528 936 25003 26489 80634 92045 84991 68137 28614 69485 20025 392 75040 10531 56314 19949 35866 36275 10345 7083...

result:

points 1.0 correct answer = 181934; correct answer = 1209576;

Test #65:

score: 50
Accepted
time: 56ms
memory: 167968kb

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:

197998 1179808
62136 12393 35601 38760 38351 12665 24849 79343 7911 48885 79144 13429 66109 68374 93865 68968 46798 59990 59558 27909 73619 59053 61441 92471 33448 38114 93521 56088 91691 89400 89146 8049 85382 17640 88627 58437 36143 95350 73303 85400 32516 51387 92437 23371 7527 73649 97568 65716 ...

result:

points 1.0 correct answer = 197998; correct answer = 1179808;

Test #66:

score: 50
Accepted
time: 64ms
memory: 167704kb

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:

187266 676668
5913 26290 85074 30904 26248 8504 30127 62743 34965 72215 17924 25620 81029 31251 88587 85835 54899 35137 16384 18790 33765 8702 63611 61699 82015 66915 81305 60630 49126 21816 47600 18125 34176 77116 45977 60398 10310 23171 60019 25477 63319 45673 4554 35423 8404 49679 60535 510 72200...

result:

points 1.0 correct answer = 187266; correct answer = 676668;

Test #67:

score: 50
Accepted
time: 64ms
memory: 166664kb

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:

147618 308338
69939 1820 63723 4774 48348 32656 50903 31543 16614 20885 26388 2245 49605 6975 48777 7119 20895 48327 48595 42894 6457 20863 1228 3170 25261 24489 51414 63115 37233 36727 55151 33584 72327 1031 45974 25502 18287 23105 8963 56163 49848 14213 66974 3714 354 7238 65153 14775 60056 33800 ...

result:

points 1.0 correct answer = 147618; correct answer = 308338;

Test #68:

score: 50
Accepted
time: 64ms
memory: 167268kb

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:

164500 943500
56909 66894 18082 25245 51340 4360 43125 73711 23576 53682 26941 18590 8603 57722 16781 58061 72405 58777 45751 64327 83267 35447 82083 33519 59553 32372 22365 2946 67488 4126 61227 33904 50292 8189 13359 75991 84095 2608 69967 19895 11078 79794 55372 15441 11553 26536 40183 21129 6541...

result:

points 1.0 correct answer = 164500; correct answer = 943500;

Test #69:

score: 50
Accepted
time: 56ms
memory: 168060kb

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:

199368 633508
20672 88505 31343 30398 64266 59191 87980 60079 30808 50980 28011 70692 32350 584 30338 70104 21567 20481 70415 6004 29065 34197 98269 85443 96936 73698 4387 84436 13542 50286 1461 91102 6317 57771 17516 28808 32024 55062 93243 60895 87792 90360 58679 73915 79395 34629 56891 17235 4230...

result:

points 1.0 correct answer = 199368; correct answer = 633508;

Test #70:

score: 50
Accepted
time: 60ms
memory: 168052kb

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:

187052 572628
23344 64783 55695 4056 21228 55403 12131 20308 61481 31705 78051 92361 30394 66997 2507 62698 77253 6177 2490 13132 92396 72564 80737 71248 47781 75489 11113 2580 11835 11752 3168 5063 23862 56444 84254 1596 35284 65695 39008 15678 54052 68064 72425 45361 24844 83795 76071 15701 63959 ...

result:

points 1.0 correct answer = 187052; correct answer = 572628;

Test #71:

score: 50
Accepted
time: 54ms
memory: 166876kb

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:

138866 431180
17987 18267 67245 5806 32282 21190 30476 9630 27760 31705 68995 53761 1017 2415 12163 41818 23267 51573 11373 38941 55713 54680 50027 40012 59492 52406 46908 69433 56726 58965 4668 54867 57881 44855 54482 26655 39421 11751 55162 15119 24383 28634 56585 10831 37922 7727 54960 6039 7238 ...

result:

points 1.0 correct answer = 138866; correct answer = 431180;

Test #72:

score: 50
Accepted
time: 63ms
memory: 167024kb

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:

157414 480886
78694 60995 45449 6644 3789 15846 20325 35905 75464 74912 10471 6290 39893 23543 2102 5376 29781 37257 65044 8887 24589 24816 19947 50741 77138 11429 43691 66804 8038 26729 64581 7192 76246 65229 17799 27765 29579 58950 4059 76437 57001 10003 77418 931 60703 8244 43320 12548 76660 1685...

result:

points 1.0 correct answer = 157414; correct answer = 480886;

Test #73:

score: 50
Accepted
time: 63ms
memory: 168056kb

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:

199190 621708
60669 15062 11011 4205 14217 87451 52751 8528 64431 6116 47710 32530 28375 93584 62537 16933 54318 20112 86581 52855 50272 41158 43668 43086 32898 95418 99562 18793 60737 34726 98619 75463 31374 1441 64493 49263 16334 8266 40143 50772 2962 59627 57339 37971 18395 84767 20266 21220 8365...

result:

points 1.0 correct answer = 199190; correct answer = 621708;

Test #74:

score: 50
Accepted
time: 51ms
memory: 168172kb

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:

182222 564658
60026 25110 51626 24837 3435 38092 73976 83731 3664 26724 78060 64804 77603 83906 57096 32370 3828 13518 19755 43796 52986 18293 3096 5105 76476 6867 6705 30805 78109 60195 50913 41091 85436 90953 31226 61059 31220 39948 47569 65467 38861 88445 54910 17631 52946 49916 30910 38751 17651...

result:

points 1.0 correct answer = 182222; correct answer = 564658;

Test #75:

score: 50
Accepted
time: 60ms
memory: 167728kb

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:

133328 2875752
40498 96421 90669 82582 80811 39691 12021 42079 84599 60416 45725 34612 15152 17977 93748 23758 85218 9705 8373 8899 81930 92198 161 25285 75075 71290 73071 51994 67162 20800 6226 35322 47681 78603 60888 71211 14613 61929 64533 61721 47309 80571 76222 30925 68091 37834 85255 38788 476...

result:

points 1.0 correct answer = 133328; correct answer = 2875752;

Test #76:

score: 25
Acceptable Answer
time: 67ms
memory: 167452kb

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:

149996 1934292
51752 99185 79761 93430 40418 43275 41214 45969 62537 8639 24407 13547 81433 4303 52781 91395 67099 81820 5811 33788 70287 53098 52303 93729 89783 39508 60530 82539 57414 64981 27803 53752 43079 1109 80934 89926 69199 53330 33525 23383 57852 67519 95474 60233 88484 61301 37082 13682 9...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 1934292;

Test #77:

score: 50
Accepted
time: 60ms
memory: 167884kb

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:

169070 977694
8289 90402 49331 84871 49335 11855 11864 36481 16270 66259 78957 74162 3037 24332 71891 6186 28350 5705 5728 21190 58019 10589 73352 49177 77695 38680 3873 14428 31188 35667 63032 44549 26073 364 17827 7222 47795 34940 91420 70417 50167 63949 92519 18505 79906 42152 4005 26984 83924 36...

result:

points 1.0 correct answer = 169070; correct answer = 977694;

Test #78:

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

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:

114280 798958
27643 14753 30163 55070 16833 9486 64773 58864 113 13953 21133 16 57580 46691 36378 35100 45109 55479 39091 10564 18355 42169 12804 26510 41538 17732 12917 13937 35688 16701 57140 33039 5818 49580 37087 38647 13030 28595 66323 65340 4503 24404 20900 1357 56837 47747 721 34782 52454 602...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 798958;

Test #79:

score: 50
Accepted
time: 62ms
memory: 167048kb

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:

136106 887574
20896 8161 73170 9820 34548 76356 68766 37953 4026 64786 43769 12771 24836 55254 41909 24464 57558 74310 65572 7273 70965 12455 43070 20694 44591 40681 20786 29876 66957 77557 56281 3071 70992 4153 37046 70096 16184 65742 5486 55956 77721 23272 74069 16940 65054 20920 48996 10401 10885...

result:

points 1.0 correct answer = 136106; correct answer = 887574;

Test #80:

score: 50
Accepted
time: 82ms
memory: 167404kb

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:

133328 2875718
15929 21115 26032 10157 17633 765 4544 36270 32505 82070 6461 60822 36007 63598 82285 568 31851 88691 65999 90163 12722 78099 98118 7993 14801 42619 85084 47830 39452 90220 41093 94010 56736 10374 60543 40961 84233 56103 99932 57506 14259 19509 41523 92758 89885 86107 37161 28937 7802...

result:

points 1.0 correct answer = 133328; correct answer = 2875718;

Test #81:

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

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:

177160 749346
20337 43931 841 5290 58563 12414 14556 47217 6078 9089 55274 84941 4642 3629 7789 17711 57459 81492 70649 74792 17637 53518 18594 90169 20541 30528 38334 27389 7680 52250 84744 88496 59960 10967 180 70942 30511 64047 18387 29353 57260 57048 53987 47136 84044 33890 70093 65876 65899 294...

result:

points 0.50 incorrect assignment Given description is not a valid permutation!; correct answer = 749346;

Test #82:

score: 50
Accepted
time: 59ms
memory: 167740kb

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:

196644 563982
7430 79936 48784 77545 96742 6625 10887 69044 51361 36709 49989 16981 74183 65370 16411 18763 59534 79741 16937 13192 80163 51850 43228 44789 19090 5934 7253 98700 24105 14239 97246 59317 89014 53071 32620 78152 31352 19705 27842 29178 3568 24366 92876 68670 53501 83798 7805 39870 5640...

result:

points 1.0 correct answer = 196644; correct answer = 563982;
English 繁體中文 简体中文

Server Time: 2024-12-02 18:37:33 | OpenSource Project