QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#706652#265. 正则二分图匹配TheZone100 ✓565ms38052kbC++232.2kb2024-11-03 12:48:212024-11-03 12:48:21

Judging History

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

  • [2024-11-03 12:48:21]
  • 评测
  • 测评结果:100
  • 用时:565ms
  • 内存:38052kb
  • [2024-11-03 12:48:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

char *p1, *p2, buf[1048577];
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
inline void Read(T &x)
{
    x = 0; char ch = gc;
    while (!isdigit(ch)) ch = gc;
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc;
}

typedef long long ll;
const int maxn = 2e6 + 5;
const int inf = 0x3f3f3f3f;

bool vis[maxn];
int to[maxn], p[maxn], mt[maxn], ans[maxn];
mt19937 rnd(time(0) ^ *(new unsigned long long));

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, d;
    Read(n), Read(d);
    for (int i = 0; i < n * d; i++) Read(to[i]), to[i]--;
    for (int i = 0; i < n; i++) p[i] = i, mt[i] = -1;
    shuffle(p, p + n, rnd);

    for (int i = 0; i < n; i++)
    {
        int u = p[i]; vector<int> q;
        while (~u)
        {
            int v = -1;
            do { v = to[u * d + rnd() % d]; } while (mt[v] == u);
            u = mt[v];
            if (!vis[v]) vis[v] = 1, q.emplace_back(v);
            else
            {
                while (q.back() != v) vis[q.back()] = 0, q.pop_back();
            }
        }

        u = p[i];
        for (int x : q) vis[x] = 0, swap(mt[x], u);
    }

    for (int i = 0; i < n; i++) ans[mt[i]] = i;
    for (int i = 0; i < n; i++) cout << ans[i] + 1 << " ";
    return 0;
}
/*#include <bits/stdc++.h>
using namespace std;

char *p1, *p2, buf[1048577];
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
inline void Read(T &x)
{
    x = 0; char ch = gc;
    while (!isdigit(ch)) ch = gc;
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc;
}

typedef long long ll;
const int maxn = 2e6 + 5;
const int inf = 0x3f3f3f3f;

bool vis[maxn];
int to[maxn], p[maxn], mt[maxn], ans[maxn];
mt19937 rnd(time(0) ^ *(new unsigned long long));

        u = p[i];
        for (int x : q) vis[x] = 0, swap(mt[x], u);
    }

    for (int i = 0; i < n; i++) ans[mt[i]] = i;
    for (int i = 0; i < n; i++) cout << ans[i] + 1 << " ";
    return 0;
}*/

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 3.0303
Accepted
time: 15ms
memory: 15868kb

input:

200000 1
4860
68405
196988
88061
63179
145556
153543
137408
73529
98133
121426
169157
139971
30468
40561
61417
2377
128946
78342
104898
53132
19812
6001
76501
144382
28176
104732
93137
81527
47685
16750
178443
30278
34394
36927
144836
113402
150495
198662
154016
49033
63788
118907
17990
25923
171718...

output:

4860 68405 196988 88061 63179 145556 153543 137408 73529 98133 121426 169157 139971 30468 40561 61417 2377 128946 78342 104898 53132 19812 6001 76501 144382 28176 104732 93137 81527 47685 16750 178443 30278 34394 36927 144836 113402 150495 198662 154016 49033 63788 118907 17990 25923 171718 199418 8...

result:

ok a perfect matching

Test #2:

score: 3.0303
Accepted
time: 33ms
memory: 15816kb

input:

100000 2
38701 64233
21385 98890
44018 45182
4039 81322
19092 98375
6549 69934
60546 82625
61820 88847
80625 98712
6227 9161
47457 91129
69077 71917
48385 81391
40048 85262
10964 28517
55941 72848
35865 43668
14735 97999
79332 90768
40710 94535
77099 85283
43429 80203
21562 48738
62878 80027
1251 44...

output:

38701 21385 44018 81322 19092 6549 60546 88847 80625 6227 47457 69077 48385 85262 10964 72848 35865 97999 79332 40710 85283 80203 21562 62878 44542 57810 77904 12003 80343 17143 9888 75542 37189 52865 7769 66178 52459 23769 5508 2035 78905 96606 14212 92309 60161 97360 84131 2831 25716 38120 20898 1...

result:

ok a perfect matching

Test #3:

score: 3.0303
Accepted
time: 20ms
memory: 13248kb

input:

66666 3
2865 7709 21957
3002 30528 66049
3259 33642 55999
27855 64335 65310
3379 7925 44323
21726 35131 35446
20806 52528 63257
6408 27039 50557
15771 37822 58917
29235 34506 64074
9789 11376 42730
6007 25251 46717
4858 28813 65939
10460 37494 38602
18356 26954 46940
20154 50645 56311
10095 17174 34...

output:

2865 66049 55999 65310 7925 21726 63257 50557 58917 29235 9789 46717 28813 37494 26954 56311 34805 27246 1802 36214 1082 50927 40571 24590 18532 46800 47712 38212 25501 27892 14263 36788 52942 24055 40834 32676 48870 41943 63154 35913 276 51908 47574 34335 28272 43328 41413 33808 43681 33775 33786 3...

result:

ok a perfect matching

Test #4:

score: 3.0303
Accepted
time: 8ms
memory: 10900kb

input:

20000 10
4453 4938 7489 8143 8851 14086 15777 15856 19810 19994
1101 1589 3045 4999 7145 8862 10949 13906 14209 19253
813 936 1987 3395 4231 9971 10028 10087 13816 17859
295 1543 6587 10106 10944 11046 12258 14673 15335 16861
1299 1466 3906 4352 4908 5370 12314 15702 16937 18602
1625 1957 1971 4818 ...

output:

15856 8862 10087 6587 3906 1957 15447 9340 4182 9944 13267 19105 13411 2879 9852 18122 10116 17823 10759 10317 13761 10752 908 9706 373 7166 1470 19655 1504 499 16311 13866 7590 6990 16698 1593 18405 16806 1522 16555 14268 14278 2423 10416 15290 16032 2230 3147 14164 16976 1864 5419 10527 2385 18130...

result:

ok a perfect matching

Test #5:

score: 3.0303
Accepted
time: 3ms
memory: 12956kb

input:

10000 20
798 829 835 1016 1195 2218 3476 3501 3863 4059 4073 4687 6721 7114 7148 7348 8500 8532 8775 9158
541 778 816 1906 2526 2578 3326 3607 4160 4522 4820 6306 6687 6923 8549 8695 8985 9347 9553 9994
159 382 543 648 1201 1650 2562 3014 3235 3376 3505 3876 5740 6798 7148 7580 8320 8525 9424 9521
2...

output:

7348 8695 3876 8252 5331 6604 6168 3798 2935 5852 1809 6461 3747 6237 855 3195 5901 7756 4161 7482 8708 1450 3860 3504 8443 4070 6987 2579 4901 7762 3125 6059 4849 7081 9747 7512 5954 5856 1650 1261 2151 1285 3855 2805 1516 9947 179 5497 9540 7745 9060 5012 164 5449 5909 4024 2333 8446 2013 9262 410...

result:

ok a perfect matching

Test #6:

score: 3.0303
Accepted
time: 0ms
memory: 12580kb

input:

4000 50
330 432 487 676 726 738 833 937 949 954 975 994 1032 1051 1099 1132 1183 1346 1547 1566 1617 1720 1721 1774 1803 1980 2193 2328 2350 2413 2426 2587 2691 2792 2976 3021 3066 3119 3171 3477 3484 3533 3577 3605 3618 3731 3803 3874 3918 3994
28 75 214 265 313 319 335 366 403 556 714 804 924 938 ...

output:

2792 3062 237 748 1572 855 2859 1632 3051 1294 2471 1515 2166 2737 2093 3730 1726 2338 2418 2247 3636 830 1060 3245 1603 3507 2764 2208 3320 2133 108 1576 3342 2382 83 202 1063 2287 2538 3750 3692 3017 3691 1872 1263 530 2808 3408 1382 372 1154 1555 3144 215 620 853 3026 1087 2043 872 960 3303 671 2...

result:

ok a perfect matching

Test #7:

score: 3.0303
Accepted
time: 0ms
memory: 14304kb

input:

2000 100
4 12 54 56 69 85 113 123 128 183 207 209 212 212 247 249 310 330 347 377 403 409 421 435 484 500 504 526 540 556 571 578 589 648 648 694 727 732 732 790 797 838 871 880 889 950 973 1018 1018 1025 1063 1109 1116 1145 1197 1230 1239 1258 1266 1268 1284 1304 1307 1376 1383 1386 1395 1404 1412 ...

output:

732 1981 675 480 1870 1720 1430 1963 878 415 281 1330 1361 1405 1988 552 645 1366 1480 179 1446 1968 588 1604 1013 209 437 1752 202 1911 518 1370 191 1217 9 103 143 642 1921 703 291 349 1737 1479 987 392 492 1123 216 1233 1590 40 877 874 116 1444 664 8 1055 190 1415 1150 951 1610 13 1766 273 115 120...

result:

ok a perfect matching

Test #8:

score: 3.0303
Accepted
time: 3ms
memory: 12664kb

input:

1000 200
3 9 11 14 28 33 35 38 44 63 74 83 83 95 100 104 106 106 109 118 128 131 132 132 140 142 143 144 145 145 145 149 150 155 161 166 167 172 173 174 174 175 183 190 194 198 201 201 203 203 204 215 217 223 225 242 248 258 267 269 272 272 275 278 281 293 297 299 318 320 334 339 343 344 344 347 348...

output:

128 108 86 180 829 42 244 544 951 356 464 218 770 650 372 58 56 57 181 516 809 859 720 944 889 562 921 574 203 775 246 161 744 607 762 479 565 802 898 953 280 537 820 345 309 313 539 15 457 643 474 973 754 117 592 187 305 774 847 119 619 276 408 764 475 126 83 482 179 586 113 332 525 893 563 62 98 9...

result:

ok a perfect matching

Test #9:

score: 3.0303
Accepted
time: 0ms
memory: 10732kb

input:

666 300
1 1 5 5 11 13 13 14 19 23 25 25 25 28 31 31 31 34 36 36 37 41 44 44 45 46 52 54 55 57 58 59 61 62 65 66 67 68 71 72 75 81 81 83 84 84 87 90 92 93 93 94 95 99 99 101 103 103 105 115 115 116 117 117 120 120 123 126 131 131 136 137 142 144 151 152 161 161 162 167 169 169 169 173 177 178 184 188...

output:

597 313 622 209 260 326 156 175 273 488 49 501 290 447 52 84 116 93 224 86 296 357 57 181 240 470 99 474 70 366 321 567 119 609 322 233 480 462 208 595 578 250 510 147 197 531 344 561 453 650 598 451 174 461 514 319 506 308 432 504 563 90 234 312 613 604 369 140 228 172 8 568 626 182 282 192 109 213...

result:

ok a perfect matching

Test #10:

score: 3.0303
Accepted
time: 2ms
memory: 10544kb

input:

20 10000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

12 10 15 17 4 3 5 16 1 9 7 6 14 8 13 18 2 20 19 11 

result:

ok a perfect matching

Test #11:

score: 3.0303
Accepted
time: 0ms
memory: 12208kb

input:

2 100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1 2 

result:

ok a perfect matching

Test #12:

score: 3.0303
Accepted
time: 2ms
memory: 12056kb

input:

1 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1 

result:

ok a perfect matching

Test #13:

score: 3.0303
Accepted
time: 228ms
memory: 38052kb

input:

2000000 1
387507
1430778
218094
455064
807442
1582214
917699
1655968
1778462
772123
268962
996042
374054
1403419
1624814
36042
813077
1143919
1473390
817258
501378
1317855
1248063
1909613
1978084
1094998
60629
101651
272496
1610999
1051528
859247
300198
1994497
245332
761294
866191
549873
1162726
40...

output:

387507 1430778 218094 455064 807442 1582214 917699 1655968 1778462 772123 268962 996042 374054 1403419 1624814 36042 813077 1143919 1473390 817258 501378 1317855 1248063 1909613 1978084 1094998 60629 101651 272496 1610999 1051528 859247 300198 1994497 245332 761294 866191 549873 1162726 403056 39135...

result:

ok a perfect matching

Test #14:

score: 3.0303
Accepted
time: 565ms
memory: 31316kb

input:

1000000 2
199363 754950
76613 628921
173375 900947
609231 802901
21413 217216
740983 755278
357523 781326
137929 439975
210831 550908
427758 764273
137762 254720
568822 871564
588642 836016
31686 707140
266427 566788
321499 905137
189618 726558
616699 630104
54080 766176
117957 586699
695703 987876
...

output:

199363 76613 900947 802901 217216 755278 357523 137929 550908 764273 137762 871564 588642 707140 266427 321499 726558 616699 54080 586699 695703 767528 977706 850365 840677 451100 91765 798274 660136 280560 138177 155987 749454 322629 938408 460261 83664 796647 956633 300748 137995 474009 63141 2766...

result:

ok a perfect matching

Test #15:

score: 3.0303
Accepted
time: 399ms
memory: 27160kb

input:

500000 4
38271 230013 254334 270640
41039 61228 344559 469434
263792 361339 441492 465652
55336 132032 276847 276901
14837 141419 213180 305018
165556 253636 256179 468748
49634 114442 197634 309934
26445 46027 179574 201044
141683 182112 384092 450681
260438 356066 389831 392443
247869 290124 41698...

output:

254334 41039 441492 55336 14837 165556 49634 201044 141683 260438 247869 282497 191935 184280 63649 157628 65848 492497 110698 170604 397873 404653 54300 68995 364565 41512 32429 392417 132676 480610 385220 29385 310947 475283 98672 115932 484531 349403 380847 58641 368842 220992 20598 66371 371245 ...

result:

ok a perfect matching

Test #16:

score: 3.0303
Accepted
time: 187ms
memory: 23380kb

input:

250000 8
2631 146917 164090 180005 186384 187359 209401 239796
19897 50857 57851 99955 119125 130482 197939 211046
61602 69725 125661 151789 152333 170938 191567 244630
28250 88386 126306 156434 209401 213742 236654 239399
4661 8624 39270 85312 106345 123219 179670 231814
3378 4520 37957 90740 10263...

output:

209401 57851 61602 126306 8624 37957 30026 192219 16906 150731 68621 6664 30882 66272 249209 135222 223335 36122 144437 97233 234560 244052 234290 154604 233154 222429 36013 95303 65105 69174 70413 78047 247441 30205 184069 205812 233638 48196 9184 246247 153546 188041 166318 165055 118414 23302 735...

result:

ok a perfect matching

Test #17:

score: 3.0303
Accepted
time: 78ms
memory: 21276kb

input:

125000 16
1740 2837 3454 4468 4752 8259 17820 35622 53227 59127 62189 70804 104178 107139 112956 115071
4672 4917 5273 8630 19872 29772 34538 45649 48808 70653 77894 79629 89198 91989 111456 112385
10180 31425 32554 33836 40036 42641 68031 69244 69346 89583 91384 91749 102500 118132 118521 120404
98...

output:

1740 4672 91384 69229 69473 117029 66010 98309 106775 100646 77146 48544 79156 34847 85911 106205 119142 76813 64847 9849 3100 26429 75395 29898 20903 45470 25532 64525 27792 76050 48449 124708 107822 18681 117804 113923 40418 61897 62314 83045 44837 54746 39310 62129 73932 25998 59571 110200 49860 ...

result:

ok a perfect matching

Test #18:

score: 3.0303
Accepted
time: 50ms
memory: 22648kb

input:

62500 32
3835 4069 6664 9493 9882 11044 12096 13503 17277 21165 21387 21724 22795 27921 28532 30505 31535 32452 33959 39348 40644 42723 43420 44352 46706 48636 52153 56846 58062 58696 59340 62159
270 3267 5060 9255 11830 12242 12358 12423 12466 14286 16368 17387 23582 23668 23942 24884 26776 31524 3...

output:

52153 37722 19979 26383 26658 13556 10055 51385 61728 16306 12311 35497 34270 16006 49836 36268 4168 5431 5926 11889 6649 30812 5941 21977 18992 51704 5099 45069 40869 14101 51540 59916 27689 44611 38834 22375 60810 33718 32658 19251 33881 52750 41132 29038 42740 15089 41532 3338 13574 38714 47617 6...

result:

ok a perfect matching

Test #19:

score: 3.0303
Accepted
time: 12ms
memory: 20668kb

input:

15625 128
51 164 216 257 339 348 735 949 1178 1284 1664 1680 1707 1781 1809 1887 2034 2323 2389 2460 2631 2889 3166 3213 3234 3270 3336 3337 3426 3430 3488 3622 3637 3764 3813 3873 3932 4215 4267 4299 4364 4501 4643 4786 5012 5030 5070 5085 5119 5187 5317 5400 5459 5730 5860 5917 6187 6410 6795 7233...

output:

3337 1172 4454 2752 4048 7814 8512 8629 9427 13899 8969 13572 5405 15217 12997 6784 14 14248 11059 1335 2716 12253 9510 5406 11717 13077 8217 2333 8699 7881 15276 685 815 12163 8763 3657 7839 168 6968 6561 14797 13244 10223 15022 12339 9852 10264 9839 6279 8151 10543 9333 7955 15485 15382 3903 14823...

result:

ok a perfect matching

Test #20:

score: 3.0303
Accepted
time: 17ms
memory: 19104kb

input:

1953 1024
1 2 4 6 8 8 9 13 15 15 17 27 31 32 34 35 35 37 38 40 40 42 45 49 50 51 52 57 61 62 63 64 67 69 70 73 79 82 82 83 86 90 91 92 94 100 101 106 106 107 109 111 113 114 116 116 118 120 120 125 127 132 140 147 148 148 153 156 158 159 159 163 165 165 168 169 169 170 170 171 172 173 174 175 176 17...

output:

1327 1178 1396 461 294 8 764 1108 659 1949 376 589 408 1907 1707 1274 270 156 1753 871 1735 1480 1648 970 298 1084 846 605 1894 12 1219 1566 1530 186 1859 81 171 911 89 1222 1588 206 519 211 860 997 364 815 1678 1468 951 967 1739 611 948 398 403 677 163 1646 318 1268 52 772 829 1389 1460 1074 1843 2...

result:

ok a perfect matching

Test #21:

score: 3.0303
Accepted
time: 6ms
memory: 19072kb

input:

244 8192
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5...

output:

174 158 226 22 60 88 179 230 196 18 139 17 5 113 93 147 211 156 100 114 10 3 197 203 119 176 195 143 11 95 65 96 64 192 126 218 50 149 201 193 150 144 138 229 132 29 57 165 146 189 131 24 148 59 62 21 128 75 35 86 108 68 31 129 107 185 81 27 116 155 23 118 141 42 223 188 55 172 97 8 175 69 39 207 15...

result:

ok a perfect matching

Test #22:

score: 3.0303
Accepted
time: 7ms
memory: 19032kb

input:

30 65536
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

9 20 24 28 3 6 25 23 4 12 16 15 27 10 18 2 14 26 17 29 5 1 11 21 8 19 30 7 13 22 

result:

ok a perfect matching

Test #23:

score: 3.0303
Accepted
time: 0ms
memory: 18600kb

input:

3 524288
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

2 1 3 

result:

ok a perfect matching

Test #24:

score: 3.0303
Accepted
time: 425ms
memory: 27964kb

input:

666666 3
3206 64240 199437
251202 414004 479216
133162 349551 525296
267125 278228 385799
255071 266873 648864
203529 309604 516958
227388 593079 647002
98211 414478 512085
200513 287454 395398
81231 139438 488811
180775 408644 487195
74579 149392 515012
466358 589635 620337
159618 186366 345229
255...

output:

64240 251202 133162 278228 648864 203529 227388 98211 200513 488811 487195 515012 620337 345229 255056 390433 91393 85393 643141 204151 554887 257693 425578 202099 265475 224107 239426 271801 106383 521357 99555 113852 160239 228118 11376 234239 466198 450386 477197 293900 181409 501288 449580 48258...

result:

ok a perfect matching

Test #25:

score: 3.0303
Accepted
time: 134ms
memory: 23924kb

input:

200000 10
2798 8208 22730 66600 119481 122650 156801 175474 177550 185015
9474 33088 52512 58337 89617 108000 129764 138027 167767 186477
2825 26827 51804 54149 80285 86265 97887 107376 141558 147823
19363 43877 45893 65333 88598 97896 108948 116509 131339 153148
33060 35928 44747 76078 78934 99908 ...

output:

66600 89617 97887 153148 192044 101045 110643 63100 55065 74964 128403 25260 69136 24619 123863 79730 164135 107387 99112 57943 54216 108919 494 117196 84730 169837 20566 49366 8511 35147 93435 137467 163151 102702 151026 47677 109164 158842 86100 98970 38158 68293 181679 161651 91467 137710 165700 ...

result:

ok a perfect matching

Test #26:

score: 3.0303
Accepted
time: 66ms
memory: 21496kb

input:

100000 20
5397 8196 10191 10507 18634 28459 29340 32559 40283 40598 53734 65521 67349 68029 69345 71483 76269 82047 84895 88672
4462 14803 19562 24889 25953 28548 32601 34192 34507 38342 48801 54116 68838 73926 78615 79627 83981 88503 90442 93297
13394 25531 37640 43005 43893 48131 51275 52948 59539...

output:

40283 38342 51275 42625 5648 88183 26907 93706 54371 738 97088 83457 83889 70099 46755 67635 7465 47350 93745 81840 10158 89161 51108 59785 53003 63987 75552 48018 42510 48012 86060 37797 18986 31717 18325 46919 2306 7868 88004 82992 64153 25789 76149 72302 27999 40815 84959 16872 1089 92812 17437 3...

result:

ok a perfect matching

Test #27:

score: 3.0303
Accepted
time: 39ms
memory: 19144kb

input:

40000 50
230 2074 4290 4458 5074 6272 7009 8092 9278 10651 11049 11356 11594 11916 14215 14942 15654 17392 18351 19069 19367 19408 20099 20658 20846 22407 23012 23933 25542 25551 25843 25941 27453 27611 28243 29369 30209 30972 31099 33489 33788 34810 34829 34849 36245 36571 37309 37983 38974 39485
1...

output:

11356 10766 28889 14217 36050 4159 37834 8706 39654 8051 26036 33908 11346 15643 27148 29044 35831 28229 5714 7193 11581 38436 28300 18079 39642 5908 30529 7561 3513 18804 16959 36058 35256 8016 3490 17042 14218 36717 9711 1836 14837 6207 26329 27087 4726 5322 37290 30994 29993 19300 10790 3767 2451...

result:

ok a perfect matching

Test #28:

score: 3.0303
Accepted
time: 25ms
memory: 20588kb

input:

20000 100
346 384 416 439 566 781 899 950 1359 1370 1969 2025 2031 2043 2510 2703 3581 3610 3956 3960 3987 4008 4035 4392 4409 4853 5049 5092 5101 5955 6051 6132 6184 6260 6463 6632 6725 6995 7298 8049 8324 8349 8720 9111 9137 9233 9328 9353 9366 9405 9427 9496 9571 9572 9588 9641 9780 9879 10102 10...

output:

18785 14590 19793 10034 7770 16538 4670 1400 2403 11175 1440 4369 19987 1867 13088 6123 19305 620 609 1467 11785 54 12499 13713 16408 9805 19161 11760 5392 559 5709 19498 11615 18651 11996 8177 1881 15052 7430 16143 610 12120 16041 2354 8578 18062 1100 19416 10294 11695 944 17087 12839 13689 8286 11...

result:

ok a perfect matching

Test #29:

score: 3.0303
Accepted
time: 20ms
memory: 19296kb

input:

6666 300
16 22 93 102 144 171 192 203 255 266 282 288 363 364 371 371 379 394 409 477 495 497 500 515 654 696 706 718 789 797 810 816 826 826 827 833 844 854 911 913 933 980 982 1006 1055 1078 1087 1116 1130 1139 1178 1245 1266 1367 1386 1447 1463 1468 1472 1489 1492 1495 1502 1513 1519 1526 1527 15...

output:

1913 3762 1493 4495 3336 4647 2846 4637 1672 4593 5094 3162 2118 5151 1826 833 296 6259 5762 3994 1730 5475 5707 5194 4880 1618 5794 6092 4798 1277 4600 1836 44 6277 1739 3500 5627 4678 2671 5566 1021 6592 2813 16 2479 1980 5967 4431 1206 3720 316 5017 2573 1384 1904 2164 6291 2457 2167 3554 2007 13...

result:

ok a perfect matching

Test #30:

score: 3.0303
Accepted
time: 12ms
memory: 19016kb

input:

2000 1000
2 3 6 14 17 20 23 23 25 25 28 30 32 32 34 36 38 39 40 41 41 42 42 48 52 52 53 54 54 54 56 60 60 60 61 61 66 67 67 68 70 72 80 83 85 86 87 89 89 90 90 91 92 95 96 98 105 108 109 110 110 113 114 116 118 119 122 124 127 130 131 132 133 134 134 135 143 147 149 152 154 156 161 163 163 165 165 1...

output:

822 690 305 1799 919 820 1966 1963 161 1396 613 418 685 1506 1043 211 1050 20 1187 1532 1988 636 857 223 811 859 1767 1588 1411 351 462 59 1101 1059 250 1599 1545 144 1267 782 1577 218 1542 127 785 662 1825 975 1024 1921 570 1714 495 61 1930 1811 1140 897 1499 538 1375 1582 331 987 278 1649 676 1125...

result:

ok a perfect matching

Test #31:

score: 3.0303
Accepted
time: 4ms
memory: 19132kb

input:

40 50000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

22 30 19 23 40 7 28 14 12 3 36 8 39 15 2 34 1 11 24 17 18 33 25 35 13 20 4 31 37 27 5 21 9 38 29 32 10 6 26 16 

result:

ok a perfect matching

Test #32:

score: 3.0303
Accepted
time: 4ms
memory: 20468kb

input:

4 500000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

4 3 1 2 

result:

ok a perfect matching

Test #33:

score: 3.0303
Accepted
time: 0ms
memory: 20588kb

input:

1 2000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

1 

result:

ok a perfect matching