QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#55286#1753. Crooked DealingMostafa_Moharram#AC ✓7ms4168kbC++171.8kb2022-10-12 22:47:572022-10-12 22:47:58

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-12 22:47:58]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 4168kb
  • [2022-10-12 22:47:57]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1000006;

int h, f[N];
vector<pair<int, int>> v;

bool check(int p) {
    vector<vector<int>> vs(p);
    int i = 0;
    for (; i < (int) v.size() and v[i].first >= p; ++i)
        for (auto &hand : vs)
            hand.push_back(v[i].second);
    for (int j = 0; i < (int) v.size(); ++i) {
        int cnt = v[i].first, val = v[i].second;
        while (cnt--) {
            vs[j].push_back(val);
            j = (j + 1) % p;
        }
    }
    for (const auto &hand : vs)
        if (hand.size() < h)
            return false;
    return true;
}

int main() {
    ios::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
    int n;
    cin >> n >> h;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        if (f[x] == 0)
            v.emplace_back(0, x);
        ++f[x];
    }
    for (auto &p : v)
        p.first = f[p.second];
    sort(v.rbegin(), v.rend());
    int l = 1, r = n, ans = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            ans = m; l = m + 1;
        } else r = m - 1;
    }
    if (ans == -1) {
        cout << "impossible\n"; return 0;
    }
//    cerr << ans << '\n';
    vector<vector<int>> vs(ans);
    int i = 0;
    for (; i < (int) v.size() and v[i].first >= ans; ++i)
        for (auto &hand : vs)
            hand.push_back(v[i].second);
    for (int j = 0; i < (int) v.size(); ++i) {
        int cnt = v[i].first, val = v[i].second;
        while (cnt--) {
            vs[j].push_back(val);
            j = (j + 1) % ans;
        }
    }
    for (const auto &hand : vs) {
        assert(hand.size() >= h);
        for (int c = 0; c < h; ++c)
            cout << hand[c] << ' ';
        cout << '\n';
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3720kb

input:

5 1
100 100 100 99 99

output:

100 
100 
100 
99 
99 

result:

ok Good Job

Test #2:

score: 0
Accepted
time: 4ms
memory: 3844kb

input:

3779 12
7986 8935 4256 9944 9331 3723 6502 786 7065 7034 10747 3375 4036 5541 3222 6012 4024 10857 9983 8474 6217 9459 7015 10729 7329 10530 10319 2021 51 3244 1842 1674 7603 966 7633 2037 4478 6177 9217 8625 9457 1561 1353 417 11104 1783 5316 5967 522 6932 9456 3698 11249 739 7449 4991 2549 4106 57...

output:

5308 9117 5210 1174 10392 9144 7750 6429 5230 3981 2675 1406 
5308 9094 5101 1157 10390 9141 7735 6426 5229 3977 2673 1404 
5308 9094 5101 1157 10387 9140 7731 6422 5227 3974 2672 1397 
5308 9073 5075 1134 10381 9138 7727 6421 5225 3972 2671 1395 
11253 9073 5075 1134 10380 9116 7725 6417 5223 3963 ...

result:

ok Good Job

Test #3:

score: 0
Accepted
time: 3ms
memory: 3696kb

input:

2500 40
3322 1903 2727 698 2388 7126 3376 5179 3963 6301 2610 763 6844 6492 179 1283 3344 114 351 6363 73 127 7371 2457 5024 2697 207 6129 5815 591 2516 241 5245 215 5734 5823 2323 276 5327 2887 5386 2329 3494 7269 4852 1497 627 2175 7229 2631 460 698 6504 7070 5220 783 4407 7415 4372 6032 5891 1732...

output:

351 3405 7399 6510 5825 5168 4434 3738 2913 2140 1058 220 7240 7012 6726 6487 6239 6018 5776 5490 5215 4992 4762 4501 4180 3931 3686 3476 3257 2963 2687 2435 2148 1940 1713 1431 1143 824 553 297 
351 3405 7372 6475 5817 5118 4407 3695 2882 2129 1045 213 7228 7007 6723 6486 6237 6017 5769 5467 5213 4...

result:

ok Good Job

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1221 29
665 2635 1289 1132 2981 2095 1197 1142 1588 219 2740 3318 1719 888 2797 2974 1967 266 781 3478 1726 731 1271 2597 2540 2895 531 1671 2001 3193 1863 3358 2667 3561 3135 1367 823 1937 2226 33 2206 1771 2976 3303 1152 886 2558 197 3230 330 1057 3150 2719 3004 2692 2816 3482 2253 2417 3003 795 2...

output:

687 1178 3134 2698 2056 1719 1142 642 269 3547 3347 3170 3001 2812 2631 2460 2304 2165 1986 1808 1624 1409 1251 1057 881 720 534 354 178 
687 1178 3110 2692 2029 1696 1112 641 266 3545 3335 3169 3000 2804 2629 2459 2298 2161 1983 1806 1619 1408 1243 1053 880 711 531 350 177 
687 1132 3110 2692 2029 ...

result:

ok Good Job

Test #5:

score: 0
Accepted
time: 7ms
memory: 3956kb

input:

9842 17
27156 5454 10038 15502 9129 5710 6001 27543 9999 8245 4371 20950 756 18278 14853 13364 18536 3840 11198 1484 27530 11284 20991 2660 21157 6521 7745 2807 9364 19609 20120 23649 22347 27031 27956 28634 4110 610 14902 18691 14351 19377 4685 24627 28985 8384 9235 24134 23608 24484 15227 18500 18...

output:

27981 27513 19882 12673 4602 28832 26260 23842 21434 19127 16729 14251 11822 9461 7098 4840 2420 
27981 27513 19882 12673 4602 28827 26259 23839 21432 19126 16727 14250 11819 9457 7093 4835 2417 
27981 27466 19828 12642 4569 28826 26254 23832 21427 19120 16719 14249 11813 9455 7086 4833 2415 
27981 ...

result:

ok Good Job

Test #6:

score: 0
Accepted
time: 6ms
memory: 4040kb

input:

8563 45
16908 16704 8430 19035 20669 20938 2051 14232 6263 12816 14080 13191 14956 25582 6234 2400 18464 4817 14014 3884 10115 14509 1927 12109 19008 16737 9755 18857 2262 11735 21949 17607 20181 22066 976 14553 1386 13168 10326 6606 9505 21300 12976 19692 16674 8379 23824 14927 18429 14604 19084 10...

output:

21077 14586 1888 23970 21806 19376 16825 14739 12704 10479 7998 5135 2798 396 25011 24137 23315 22511 21712 20926 20094 19178 18368 17615 16888 16108 15314 14514 13768 12913 12174 11379 10569 9746 8938 8160 7310 6543 5743 4948 4100 3287 2508 1614 867 
21077 14586 1888 23939 21762 19365 16816 14730 1...

result:

ok Good Job

Test #7:

score: 0
Accepted
time: 2ms
memory: 4000kb

input:

7283 33
8666 2529 6912 20909 6554 9542 20897 3828 3255 15698 20715 6935 3031 8141 21462 16042 17692 5353 15551 5509 18683 16330 9594 18629 16677 1797 10861 8150 18767 5451 599 12451 17793 17532 2823 3566 21165 100 6537 19254 5549 44 18606 15273 6915 8049 11843 7533 13879 6724 21196 3500 8018 9879 18...

output:

21070 10251 20953 17843 14764 11919 8916 6127 3657 737 21129 20068 19022 18119 17238 16360 15596 14635 13691 12808 11900 10960 10088 9188 8293 7358 6455 5500 4634 3686 2757 1859 930 
21070 10251 20902 17837 14742 11903 8887 6095 3652 693 21116 20066 19011 18117 17221 16359 15595 14625 13687 12805 11...

result:

ok Good Job

Test #8:

score: 0
Accepted
time: 5ms
memory: 3972kb

input:

6004 21
2433 10470 5485 3115 14326 1052 15005 14344 975 16897 6271 2186 12524 13498 13003 6755 16223 5448 15814 6360 5700 16751 14467 4213 14169 9239 11068 216 11345 760 3610 8183 15186 13435 3969 13688 15913 8943 3538 9102 2485 3151 3566 11374 17722 7396 2822 1954 9962 847 3554 16697 4357 5936 1603...

output:

10803 17822 13911 10260 6811 3343 17920 16671 15435 14327 13151 11954 10787 9656 8478 7378 6073 4854 3727 2501 1276 
10803 17801 13911 10254 6811 3335 17918 16670 15431 14326 13150 11950 10785 9654 8477 7376 6070 4853 3722 2498 1275 
10803 17801 13908 10254 6807 3335 17908 16666 15426 14324 13141 11...

result:

ok Good Job

Test #9:

score: 0
Accepted
time: 4ms
memory: 3792kb

input:

4725 10
12382 664 4149 5513 4122 9640 10059 5919 13598 2236 10606 13116 3570 1788 6542 225 14057 5102 627 6436 11026 1597 2371 8720 11482 13376 10375 9227 5681 11834 5294 4801 12359 9772 4416 5056 11315 14012 1328 1835 311 4930 7717 7994 9233 6419 10933 12363 6675 11146 6018 9834 1657 2934 13173 126...

output:

12515 11693 5505 13882 11816 9755 7815 5906 3945 2019 
12515 11693 5505 13878 11815 9750 7809 5902 3943 2017 
12515 11686 5407 13875 11813 9741 7806 5890 3942 2014 
12515 11686 5407 13868 11812 9739 7803 5887 3933 2009 
11343 11676 5396 13867 11809 9734 7802 5885 3932 2005 
11343 11676 5396 13866 11...

result:

ok Good Job

Test #10:

score: 0
Accepted
time: 4ms
memory: 3800kb

input:

3446 38
6327 5297 2904 6253 8128 3119 6061 401 8937 3901 1533 7539 8358 5199 2079 6789 854 4315 2176 5738 2473 3052 5493 10301 8616 3870 8780 2997 1775 6488 5649 2307 9311 6542 4164 9856 7371 4967 10245 7790 9365 5383 9210 5132 3296 5118 3989 6573 4019 5433 6738 4762 10254 872 10010 7792 1313 3863 1...

output:

2822 5336 9824 8585 7229 6108 5025 3813 2684 1664 756 10245 9859 9531 9194 8803 8413 8012 7624 7206 6836 6506 6148 5775 5426 4973 4567 4242 3907 3479 3134 2759 2418 2026 1698 1275 898 506 
2822 5336 9824 8585 7229 6108 5025 3813 2684 1664 756 10237 9849 9530 9191 8793 8412 8009 7620 7199 6831 6504 6...

result:

ok Good Job

Test #11:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

2167 26
2278 6357 1750 5337 1831 6003 3009 4290 5004 3881 3565 3467 2373 5719 6116 1934 1129 3088 2449 4265 4554 3107 5822 2455 5570 5233 6285 6039 6128 2732 4677 700 6042 3747 3211 3576 4081 6322 5774 2455 5135 4509 1543 2788 6411 3493 4 2598 1993 1722 5714 1479 5635 6253 47 2717 3184 1 1281 6037 1...

output:

6463 472 5719 4781 3490 2436 1341 602 6368 5983 5606 5202 4890 4505 4129 3778 3493 3107 2795 2448 2095 1741 1407 1085 721 349 
6463 87 5714 4781 3486 2436 1335 602 6367 5979 5602 5201 4880 4504 4120 3776 3482 3105 2790 2446 2094 1736 1405 1075 714 346 
6463 87 5714 4772 3486 2432 1335 582 6365 5977 ...

result:

ok Good Job

Test #12:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

888 14
237 1182 686 98 2070 1452 905 749 1798 2176 2527 899 2455 684 1813 2500 705 1419 1447 2017 432 1760 692 2022 2345 628 224 1513 1901 568 2378 2643 2553 1385 1559 391 1446 1237 2093 5 1795 2309 1556 963 1742 1544 1639 435 598 11 283 2649 1976 2236 123 219 2272 1670 730 2515 1782 454 2113 2234 1...

output:

2571 2319 1657 959 2646 2375 2140 1852 1599 1333 1021 749 502 252 
2571 2309 1657 829 2644 2373 2131 1849 1597 1330 1019 748 492 250 
2571 2309 1637 829 2640 2370 2128 1846 1594 1320 1015 746 481 246 
2422 2297 1637 811 2636 2367 2118 1842 1591 1319 1013 741 475 243 
2422 2297 1607 811 2634 2363 211...

result:

ok Good Job

Test #13:

score: 0
Accepted
time: 3ms
memory: 4168kb

input:

9509 42
23600 25927 7002 7210 7769 4756 6161 25739 16545 1033 9936 4025 13639 18064 11980 16518 10142 16826 20230 24471 17778 24050 17789 3999 25772 19008 5746 5899 13817 159 1866 25003 28152 13212 19292 21210 13043 27280 19475 17852 15912 1121 26536 8379 9157 17736 6554 26441 4058 21205 9508 21708 ...

output:

2962 13686 27874 25002 22112 19692 17161 14137 11259 8670 6043 3325 450 27795 26808 25912 25005 24123 23204 22242 21228 20079 19148 18159 17203 16346 15490 14511 13623 12699 11724 10687 9784 8763 7760 6845 5827 4828 3814 2897 1964 1049 
2962 13686 27874 25002 22112 19692 17161 14137 11259 8670 6043 ...

result:

ok Good Job

Test #14:

score: 0
Accepted
time: 1ms
memory: 4112kb

input:

8230 30
13968 9244 5768 11573 18956 19465 2286 12924 11978 6316 18477 23333 856 247 3940 5428 11023 15981 21613 23672 2088 634 24385 12874 22883 2395 7872 20881 6302 19709 5887 18787 386 10039 18948 8400 9184 11067 14318 6170 10907 5239 6830 5585 24404 16393 20847 17050 1484 11915 13839 13031 12137 ...

output:

24106 6854 22079 18680 14962 11713 8874 5169 1899 24187 23172 21980 20806 19678 18511 17385 16284 15018 13838 12672 11571 10379 9200 8060 6922 5795 4638 3429 2303 1175 
24106 6854 22043 18597 14934 11685 8840 5159 1888 24182 23171 21979 20804 19673 18509 17383 16278 15017 13830 12661 11567 10377 919...

result:

ok Good Job

Test #15:

score: 0
Accepted
time: 3ms
memory: 3972kb

input:

6951 19
6344 17515 4626 14278 5487 8551 20210 3016 8139 9914 3094 15618 12329 8065 18751 17947 11207 14696 868 1245 11384 4343 7335 18824 19814 11004 9096 10108 545 12323 8579 13457 925 7300 17905 19538 5979 19606 9950 18225 6792 8030 12993 3308 13676 14726 9571 9473 20393 4626 16426 6143 7644 9829 ...

output:

18918 20195 15542 10881 6092 864 19751 18302 16760 15383 13791 12296 10840 9382 7825 6308 4805 3213 1600 
18918 20195 15527 10881 5998 864 19750 18299 16748 15378 13782 12292 10838 9379 7823 6304 4796 3206 1597 
18918 20159 15527 10862 5998 863 19748 18296 16729 15374 13779 12291 10828 9373 7819 630...

result:

ok Good Job

Test #16:

score: 0
Accepted
time: 5ms
memory: 3900kb

input:

5672 47
726 5197 3574 15326 12907 540 14392 13031 5028 11827 9332 9409 2515 12992 10870 8533 10693 12970 3537 2734 124 6652 12180 4832 16566 16308 9420 2105 13563 6528 9945 9015 1244 4995 16162 9080 3428 7354 6371 8475 3568 9494 16497 1550 5501 12735 1252 3709 15243 16354 254 1045 4109 5934 3431 125...

output:

16726 9462 675 15393 13846 12356 11003 9560 8013 6354 5109 3698 2171 597 16741 16230 15705 15195 14701 14199 13740 13242 12753 12251 11755 11233 10673 10196 9722 9219 8766 8278 7815 7329 6843 6300 5739 5169 4689 4179 3651 3140 2646 2109 1593 1132 590 
16726 9462 675 15392 13817 12355 10966 9550 7970...

result:

ok Good Job

Test #17:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

4393 35
10294 10161 2612 1537 3347 8611 9520 5100 2644 12055 12500 4703 9283 1849 4987 1875 9481 10803 4930 3448 6176 7559 1053 8767 13138 5128 8843 10051 7485 2324 9982 5459 1343 3123 540 1718 1532 12179 3580 1610 1234 9632 4164 311 13056 10420 9070 12937 10723 9230 3191 10915 1535 2980 3170 5312 8...

output:

10938 4824 12202 10307 8651 6921 5238 3801 1918 371 12765 12220 11749 11236 10692 10223 9722 9248 8773 8203 7689 7230 6692 6165 5673 5157 4663 4128 3615 3117 2605 2079 1522 1028 542 
10938 4502 12179 10307 8603 6921 5230 3801 1896 371 12759 12219 11744 11229 10682 10212 9718 9244 8771 8193 7687 7227...

result:

ok Good Job

Test #18:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

3114 23
4854 2210 1741 3107 7001 2570 5596 76 988 1255 3256 1503 2438 4831 1103 7315 7570 8195 5048 3387 8688 7064 4148 434 189 7658 7365 3752 3166 9053 8692 2790 1221 1686 1235 6792 290 3887 1578 6972 9133 8443 6188 8931 6148 7781 2829 6963 6834 4107 4385 5559 9262 967 2611 629 272 3599 6860 349 24...

output:

9297 613 7762 6279 4736 2848 1243 9228 8678 8149 7541 6936 6400 5747 5214 4540 3953 3347 2757 2225 1656 1095 536 
9297 613 7748 6279 4703 2848 1234 9224 8658 8148 7540 6935 6397 5746 5208 4535 3944 3342 2754 2218 1655 1092 534 
9297 604 7748 6266 4703 2830 1234 9218 8652 8147 7530 6928 6395 5743 519...

result:

ok Good Job

Test #19:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

1835 11
1421 3865 961 3020 1348 4937 2618 3465 61 1949 4121 5311 4501 4921 4722 2334 4962 5146 3890 2552 2155 5168 4449 2355 240 1379 4987 224 604 4193 570 1008 878 682 1230 1783 5207 4999 365 2039 4743 422 49 4891 1792 4818 5051 2802 3575 985 3835 1992 4770 5400 1753 4027 2158 64 4465 291 3794 65 1...

output:

386 4724 2721 800 5085 4444 3740 3022 2213 1508 788 
386 4702 2718 781 5082 4440 3738 3020 2212 1504 785 
386 4702 2718 781 5080 4437 3736 3019 2210 1493 783 
386 4638 2708 769 5079 4429 3735 3011 2209 1488 779 
269 4638 2708 769 5073 4428 3731 3002 2208 1487 777 
269 4627 2680 732 5070 4426 3730 30...

result:

ok Good Job

Test #20:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

556 40
1663 280 272 1276 1235 865 588 418 1529 957 248 1283 624 452 997 108 1656 1655 1456 942 1423 203 288 1350 112 1137 39 1134 1469 925 462 113 314 113 525 1536 1436 668 1607 1659 1244 417 593 1370 1657 1531 888 455 946 1532 1541 215 1237 1432 596 660 1259 1065 1481 114 202 935 441 1625 1154 246 ...

output:

1659 1128 624 1603 1502 1361 1240 956 613 525 314 41 1639 1579 1535 1485 1423 1379 1348 1292 1242 1200 1131 1065 1014 953 916 870 796 740 685 634 586 521 462 429 374 288 248 204 
1659 1128 113 1603 1494 1361 1152 956 611 525 296 41 1637 1577 1533 1481 1421 1378 1343 1290 1241 1198 1125 1063 1010 951...

result:

ok Good Job

Test #21:

score: 0
Accepted
time: 7ms
memory: 3924kb

input:

9177 28
20232 17428 4155 26994 6484 3856 6297 23998 22610 21836 15103 15765 25620 17823 9274 19421 2291 1364 1074 18319 8645 8368 14762 5238 2487 3077 3869 8768 17937 9554 12373 26208 5971 297 11170 14239 21342 24556 23694 17029 17331 11627 19319 20741 18180 26417 4039 1002 13352 18099 4155 24651 16...

output:

25260 6246 24317 20093 16109 12332 8270 4044 41 26234 24906 23555 22159 20690 19286 17972 16681 15245 13840 12562 11177 9869 8512 7213 5800 4421 3009 1588 
25260 6246 24317 20085 16109 12306 8270 4039 41 26233 24902 23545 22158 20684 19278 17962 16679 15242 13835 12559 11176 9862 8504 7212 5796 4413...

result:

ok Good Job

Test #22:

score: 0
Accepted
time: 6ms
memory: 3928kb

input:

7898 16
11215 2335 3296 4655 17318 18049 2496 11678 17212 302 22477 8923 11542 572 1812 8204 4127 2536 4863 18158 18371 11529 21331 13541 2694 12853 6111 22686 10009 3310 14747 19818 5820 22610 11773 2699 16348 9096 17957 5749 12166 14103 1141 16250 7766 42 18039 18957 9544 9399 8959 15690 11638 145...

output:

22801 21614 15138 9336 3532 22908 20967 18835 16814 14609 12523 10468 8463 6339 4300 2234 
22801 21582 15138 9321 3532 22905 20966 18829 16813 14600 12521 10467 8462 6337 4298 2229 
22801 21582 15108 9321 3486 22901 20964 18827 16812 14597 12518 10455 8461 6330 4297 2226 
22801 21581 15108 9314 3486...

result:

ok Good Job