QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#478814 | #265. 正则二分图匹配 | A_programmer# | 100 ✓ | 576ms | 37900kb | C++17 | 1.4kb | 2024-07-15 11:27:05 | 2024-07-15 11:27:06 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 3.0303
Accepted
time: 23ms
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: 29ms
memory: 16724kb
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 82625 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 77366 14212 92309 60161 97360 84131 2831 25716 38120 20898 1...
result:
ok a perfect matching
Test #3:
score: 3.0303
Accepted
time: 18ms
memory: 13016kb
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:
7709 3002 3259 64335 44323 35446 52528 50557 58917 34506 9789 46717 65939 38602 46940 50645 17174 52076 5195 21328 59655 50927 40571 47027 31863 27065 47712 64048 25501 59559 4713 52945 37938 24055 40834 46125 39223 66265 63154 35913 10873 51908 47574 34335 16498 43328 41413 3746 43681 61505 33786 3...
result:
ok a perfect matching
Test #4:
score: 3.0303
Accepted
time: 4ms
memory: 13020kb
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:
19810 1101 17859 11046 5370 17860 10707 14381 18325 16354 6770 19105 17729 12845 12606 13513 4041 5490 4695 2135 6495 7303 5850 5974 13282 7166 17697 17253 4896 16018 13402 1613 4500 6541 3599 10358 2505 19353 19832 2391 13099 11859 8507 18658 13312 9803 11270 435 10104 2126 15567 19505 2347 1087 81...
result:
ok a perfect matching
Test #5:
score: 3.0303
Accepted
time: 3ms
memory: 14324kb
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:
4059 4522 3876 7431 3454 3949 3836 3927 6255 6838 6408 6249 5027 7662 6935 2649 3550 6831 7971 6738 654 2128 789 3504 9984 4741 2090 2081 8699 6007 3467 2857 4849 17 282 6138 4851 5656 1129 1521 1756 2571 3880 2934 7381 5904 9245 2793 5569 2009 2965 8379 4380 1323 3471 9523 1687 1260 7388 8432 9372 ...
result:
ok a perfect matching
Test #6:
score: 3.0303
Accepted
time: 4ms
memory: 14088kb
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:
3994 2832 1786 2857 3511 1767 1746 3100 536 3220 746 3139 1311 1211 3910 259 111 3620 3578 1972 3224 2984 3682 2677 792 866 1700 1657 3132 814 184 773 435 1739 3434 3432 966 2736 3368 3959 826 774 1664 3898 2519 530 2921 195 3677 908 1178 384 66 1375 2992 655 38 3873 1143 248 200 2474 1554 542 1152 ...
result:
ok a perfect matching
Test #7:
score: 3.0303
Accepted
time: 0ms
memory: 12312kb
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:
1395 1303 1440 847 1957 1499 550 8 1740 1588 1982 642 1370 1747 1587 1620 907 1889 1529 565 228 214 606 1088 1785 1014 1350 1969 198 1940 489 1265 1045 188 1748 165 466 1174 404 1600 23 1925 256 877 987 898 1235 1837 983 1741 1819 868 1751 1772 1175 224 524 743 1675 1743 330 1320 1263 1301 451 255 5...
result:
ok a perfect matching
Test #8:
score: 3.0303
Accepted
time: 3ms
memory: 12708kb
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:
458 51 168 614 973 558 902 491 145 633 580 873 78 728 760 393 794 532 511 117 589 347 988 809 724 928 246 681 441 732 93 674 877 204 103 702 182 744 869 739 211 478 24 450 80 660 18 120 550 847 628 399 932 573 212 201 646 260 114 949 938 285 167 868 105 863 350 707 610 430 6 856 303 984 230 316 322 ...
result:
ok a perfect matching
Test #9:
score: 3.0303
Accepted
time: 0ms
memory: 10736kb
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:
579 17 661 20 271 199 513 514 247 526 402 188 131 94 592 21 433 568 394 135 464 269 67 336 209 239 481 377 344 91 272 626 482 105 151 323 270 525 157 595 134 222 298 165 553 116 575 127 468 366 329 313 171 537 88 653 334 407 121 650 662 354 292 500 293 462 422 376 102 183 103 161 409 215 223 278 475...
result:
ok a perfect matching
Test #10:
score: 3.0303
Accepted
time: 0ms
memory: 12332kb
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:
6 20 2 14 4 8 11 19 9 1 17 10 7 15 12 18 16 13 3 5
result:
ok a perfect matching
Test #11:
score: 3.0303
Accepted
time: 2ms
memory: 12268kb
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:
2 1
result:
ok a perfect matching
Test #12:
score: 3.0303
Accepted
time: 0ms
memory: 10204kb
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: 286ms
memory: 37900kb
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: 576ms
memory: 31992kb
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 566788 321499 726558 616699 54080 586699 695703 767528 977706 94468 840677 451100 91765 798274 660136 280560 138177 155987 749454 322629 938408 232092 83664 796647 66848 300748 137995 474009 63141 276683...
result:
ok a perfect matching
Test #15:
score: 3.0303
Accepted
time: 358ms
memory: 25392kb
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:
230013 41039 441492 276847 305018 253636 197634 46027 182112 260438 290124 288890 160039 184280 6306 368334 113288 383179 110698 187536 255210 5997 435471 68995 498607 263970 32429 36726 200017 480610 85438 223611 142095 181407 414682 430620 97132 349403 202093 58641 307776 385474 447977 66371 42026...
result:
ok a perfect matching
Test #16:
score: 3.0303
Accepted
time: 160ms
memory: 21332kb
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:
2631 130482 69725 209401 123219 232844 106979 135533 172972 54169 21290 150215 170786 51878 243246 135222 213987 5567 10684 20209 27329 238410 234290 30362 214765 90018 115451 246848 242568 84419 219043 46350 144574 126663 238335 88667 233638 39100 88967 122907 6823 170609 65782 97989 187588 8271 22...
result:
ok a perfect matching
Test #17:
score: 3.0303
Accepted
time: 79ms
memory: 21584kb
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:
53227 29772 42641 121687 27953 75637 69911 8984 100131 94725 32399 71707 73948 18398 24657 3749 42661 85862 30730 84460 2928 108232 65990 65781 91946 13354 63023 56263 71690 76050 69893 58333 119686 21690 34276 4435 43703 87634 63290 22645 51480 16896 124023 24527 50159 2498 62069 98071 42990 18224 ...
result:
ok a perfect matching
Test #18:
score: 3.0303
Accepted
time: 51ms
memory: 19360kb
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:
48636 5060 24785 28186 5095 55223 5887 34600 40226 35737 19839 45938 3223 30300 17049 51297 46527 34029 10695 55059 34301 25854 7419 42220 48818 46179 6770 6043 26674 48566 14161 34367 40986 39921 24965 5123 48070 9995 41943 43156 11944 18702 7354 54072 25575 5858 30662 17961 16230 53224 60703 50132...
result:
ok a perfect matching
Test #19:
score: 3.0303
Accepted
time: 7ms
memory: 20612kb
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:
14323 9127 3424 11274 10259 6611 7330 13128 5164 11546 8981 13954 7566 9881 12298 3980 7225 4946 5638 2086 9631 14116 1555 4300 165 2178 5265 10959 5796 9316 8589 8147 15329 3409 13135 4819 14709 13843 3155 14049 9134 10309 2181 7632 3064 4655 1041 755 8949 6383 14428 13264 7955 12341 3830 2524 5005...
result:
ok a perfect matching
Test #20:
score: 3.0303
Accepted
time: 13ms
memory: 19292kb
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:
719 676 47 1060 1596 701 687 690 311 1841 791 1037 1894 1893 1737 905 333 888 749 683 94 682 1116 1318 1866 1450 878 879 717 41 1527 1073 455 45 1927 851 319 1520 1835 450 1617 1002 1270 1861 1942 1626 649 525 696 1249 1947 128 374 201 1064 1126 152 1599 673 129 1530 1399 73 665 1852 866 902 75 949 ...
result:
ok a perfect matching
Test #21:
score: 3.0303
Accepted
time: 3ms
memory: 20120kb
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:
210 227 146 101 14 132 100 39 195 181 173 17 237 156 6 234 194 50 113 168 199 80 93 121 139 174 193 239 125 170 136 135 111 185 22 169 152 36 97 45 72 12 144 28 55 62 182 134 109 208 204 64 148 201 40 171 26 114 54 183 119 15 138 191 56 149 46 76 110 128 94 244 198 59 165 222 32 105 160 187 141 231 ...
result:
ok a perfect matching
Test #22:
score: 3.0303
Accepted
time: 11ms
memory: 20348kb
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:
11 24 18 16 29 25 21 8 5 3 4 13 23 15 7 1 20 14 9 19 17 28 30 22 26 6 2 10 12 27
result:
ok a perfect matching
Test #23:
score: 3.0303
Accepted
time: 9ms
memory: 17236kb
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:
1 3 2
result:
ok a perfect matching
Test #24:
score: 3.0303
Accepted
time: 452ms
memory: 29108kb
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 525296 278228 255071 203529 593079 512085 200513 488811 408644 149392 620337 159618 255056 203276 231281 227367 491616 135998 63789 578479 122992 75664 136399 381924 578299 406143 351294 201039 99555 113852 160239 227431 11376 234239 466198 450386 616163 108473 578702 501288 449580 4825...
result:
ok a perfect matching
Test #25:
score: 3.0303
Accepted
time: 122ms
memory: 21872kb
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:
122650 108000 107376 116509 99908 61426 81072 134409 2119 140958 128403 35093 72561 91346 123863 26730 164135 97529 86214 175858 146905 5356 191368 24627 82944 46812 28909 162706 153862 131646 46341 151609 14175 81049 70347 38729 113972 175867 75624 63127 90225 49503 181679 32824 198293 76009 165700...
result:
ok a perfect matching
Test #26:
score: 3.0303
Accepted
time: 70ms
memory: 22740kb
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:
76269 24889 59539 58421 59387 84675 89781 62649 44605 56767 397 19652 88207 25403 60468 9713 47200 45463 60714 55619 51248 60604 20289 7828 85712 45030 38111 78901 38237 88516 15148 61443 1056 74005 48741 69080 26144 19494 44185 29715 62383 91612 56852 1703 1736 85652 56646 15510 23389 9871 58456 22...
result:
ok a perfect matching
Test #27:
score: 3.0303
Accepted
time: 33ms
memory: 20640kb
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:
34829 35878 13166 3520 27345 12643 17336 18934 14029 21770 32916 21219 38744 30078 11427 36122 16752 11930 8418 12455 8110 34632 5508 10873 5464 38852 1167 7561 22146 29100 4874 28751 27835 34278 8411 25277 34609 12630 25311 23653 20098 37875 5372 2727 28574 26552 37435 36563 6925 28735 38150 15 380...
result:
ok a perfect matching
Test #28:
score: 3.0303
Accepted
time: 18ms
memory: 19140kb
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:
17082 10436 6887 5313 154 1522 1887 14983 18621 1700 19983 1369 7085 14033 8013 727 7899 1177 19240 10445 14645 19205 16110 13568 11065 19857 12297 14242 18952 851 10635 6143 4034 1575 18797 14507 11895 19614 1421 2106 13507 12376 9774 660 9234 625 3186 9600 5928 3028 19642 1931 6874 7278 5795 17915...
result:
ok a perfect matching
Test #29:
score: 3.0303
Accepted
time: 11ms
memory: 19084kb
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:
2101 1610 6478 903 4297 3806 1636 709 728 4111 4342 2920 5608 5645 13 5477 4134 224 3270 3725 4413 3191 3274 1744 6459 3205 589 281 2472 2008 5888 3225 5383 5471 4755 2279 2544 4678 6077 6265 4867 2840 2100 526 1475 782 3831 1013 6318 3930 433 2364 6119 3863 5057 192 5565 686 1195 3351 1623 458 4575...
result:
ok a perfect matching
Test #30:
score: 3.0303
Accepted
time: 7ms
memory: 18992kb
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:
689 1477 561 1408 1492 173 206 1592 726 37 87 1487 1356 416 214 1985 522 65 1735 1095 1159 1476 229 130 1857 469 749 276 1070 1437 1896 847 604 1211 977 790 596 489 733 706 45 305 230 474 1630 343 492 985 891 667 1643 147 1969 1653 950 747 133 549 1193 78 1917 375 603 3 280 1189 59 146 1964 611 303 ...
result:
ok a perfect matching
Test #31:
score: 3.0303
Accepted
time: 0ms
memory: 20700kb
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:
6 1 10 37 36 40 22 13 14 16 21 29 7 9 27 28 3 5 19 26 15 33 39 11 38 30 34 31 17 32 18 35 12 23 4 25 8 24 20 2
result:
ok a perfect matching
Test #32:
score: 3.0303
Accepted
time: 6ms
memory: 19248kb
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: 3ms
memory: 19000kb
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