QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51097#1282. Necklaceckiseki#TL 658ms4068kbC++5.9kb2022-09-30 19:18:192022-09-30 19:18:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-30 19:18:22]
  • 评测
  • 测评结果:TL
  • 用时:658ms
  • 内存:4068kb
  • [2022-09-30 19:18:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
static constexpr lld INF = lld(1) << 60;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<pair<int,int>> a(n);
        for (auto &[ai, _] : a) cin >> ai;
        for (auto &[_, ai] : a) cin >> ai;
        vector<vector<pair<lld, int>>> v(n);
        for (int i = 0; i < n; ++i) {
            v[a[i].first - 1].emplace_back(a[i].second, i);
        }
        for (auto &vi : v) sort(vi.begin(), vi.end(), greater<>());

        vector<pair<int64_t,int>> nsm;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < int(v[i].size()); ++j) {
                if (v[i][j].first >= 0) continue;
                nsm.emplace_back(v[i][j].first, i);
            }
        }
        sort(nsm.begin(), nsm.end(), greater<>());
        vector<vector<int>> np(n);
        vector<vector<int64_t>> nps(n);
        for (int i = 0; i < int(nsm.size()); ++i) {
            np[nsm[i].second].push_back(i);
            nps[nsm[i].second].push_back(nsm[i].first);
            if (i > 0) {
                nsm[i].first += nsm[i - 1].first;
            }
        }
        for (int i = 0; i < n; ++i) {
            for (size_t j = 1; j < nps[i].size(); ++j) {
                nps[i][j] += nps[i][j - 1];
            }
        }
        auto get_k = [&nsm, &np, &nps](int i, int k) {
            if (nsm.size() - np[i].size() < k) return -INF;
            size_t l = 0, r = nsm.size();
            while (r - l > 1) {
                size_t m = (l + r) >> 1;
                auto it = upper_bound(np[i].begin(), np[i].end(), m);
                size_t d = m - (it - np[i].begin()) + 1;
                if (d <= k) l = m;
                else r = m;
            }
            auto it = upper_bound(np[i].begin(), np[i].end(), l);
            auto ret = nsm[l].first;
            if (it != np[i].begin()) {
                ret -= nps[i][prev(it) - np[i].begin()];
            }
            return ret;
        };

        vector<pair<lld,int>> psm(n + 1);
        for (auto &vi : v) {
            lld csm = 0;
            int l = 0;
            int j;
            for (j = 0; j < int(vi.size()); ++j) {
                if (vi[j].first < 0) {
                    break;
                }
                ++l;
                csm += vi[j].first;
                psm[j + 1].first += csm;
                psm[j + 1].second += l;
            }
            while (j < n) {
                psm[j + 1].first += csm;
                psm[j + 1].second += l;
                ++j;
            }
        }

        tuple<lld, int, int> ans = {-INF, -1, -1};

        for (int i = 0; i < n; ++i) {
            lld ns = 0;
            int nc = 0;
            for (int j = 0; j < int(v[i].size()); ++j) {
                auto cv = v[i][j].first;
                if (cv < 0) {
                    ns += cv;
                    nc++;
                }
                lld cs = psm[j + 1].first + ns;
                int cl = psm[j + 1].second + nc;
                if (j == 0 and cl <= 2) continue;
                if (cs <= get<0>(ans)) continue;
                if ((j + 1) > cl / 2) {
                    int k = (j + 1) * 2 - cl;
                    auto vk = get_k(i, k);
                    if (vk == -INF) continue;
                    cs += vk;
                }
                
                tuple<lld, int, int> cans = {cs, i, j + 1};
                ans = max(ans, cans);
            }
        }

        auto [s, c, l] = ans;

        vector<pair<int64_t, int>> meow;
        for (int i = 0; i < n; ++i) {
            if (v[i].empty()) continue;
            meow.emplace_back(v[i][0].first, i);
        }
        sort(meow.begin(), meow.end(), greater<>());
        if (meow.size() >= 3 and meow[0].first + meow[1].first + meow[2].first > s) {
            cout << 3 << '\n';
            cout << v[meow[0].second][0].second + 1 << ' ' << v[meow[1].second][0].second + 1 << ' ' << v[meow[2].second][0].second + 1 << '\n';
            continue;
        }

        if (s == -INF) {
            cout << -1 << '\n';
        } else {
            vector<int> p(n);
            for (int i = 0; i < n; ++i) {
                p[i] = min<int>(l, v[i].size());
                if (i != c) {
                    for (int j = 0; j < l; ++j) {
                        if (j == v[i].size()) break;
                        if (v[i][j].first < 0) {
                            p[i] = j;
                            break;
                        }
                    }
                }
            }
            int totl = accumulate(p.begin(), p.end(), 0);
            if (l > totl / 2) {
                priority_queue<pair<int64_t,int>> pq;
                for (int i = 0; i < n; ++i) {
                    if (i == c) continue;
                    if (p[i] < v[i].size()) {
                        pq.emplace(v[i][p[i]].first, i);
                    }
                }
                while (l > totl / 2) {
                    totl++;
                    auto [_, i] = pq.top(); pq.pop();
                    p[i]++;
                    if (p[i] < v[i].size()) {
                        pq.emplace(v[i][p[i]].first, i);
                    }
                }
            }

            vector<vector<int>> o(l); 
            size_t cp = 0;
            for (int i = 0; i < n; ++i) {
                if (i == c) continue;
                for (int j = 0; j < p[i]; ++j) {
                    o[cp].push_back(v[i][j].second);
                    if (++cp == l) cp = 0;
                }
            }
            vector<int> seq;
            for (size_t i = 0; i < l; ++i) {
                seq.push_back(v[c][i].second);
                for (auto x : o[i]) seq.push_back(x);
            }
            cout << seq.size() << '\n';
            for (size_t i = 0; i < seq.size(); ++i)
                cout << seq[i] + 1 << " \n"[i + 1 == seq.size()];
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3572kb

input:

4
4
1 1 1 1
1 2 3 4
4
1 1 2 2
1 2 3 4
8
2 6 5 4 3 1 7 7
-1 4 -1 2 10 -1 3 0
6
5 5 3 3 4 6
5 8 0 -1 -2 -7

output:

-1
4
2 4 1 3
4
5 4 2 7
4
2 3 1 4

result:

ok 4 cases.

Test #2:

score: 0
Accepted
time: 98ms
memory: 3668kb

input:

36398
6
4 6 4 4 5 2
7 -9 -9 4 -1 -8
2
1 1
-8 -5
2
2 1
10 7
9
5 6 5 8 2 3 3 7 8
-7 5 -5 7 8 7 -5 -5 8
2
1 2
6 -8
9
2 3 3 5 3 9 3 9 3
5 2 -2 5 -8 -5 -3 6 -2
4
4 2 4 1
-1 -1 10 -4
4
3 1 2 1
-9 -6 4 10
5
4 3 4 1 4
-8 1 6 10 -8
6
2 6 3 5 4 1
1 -7 4 0 6 -6
6
6 6 5 2 1 2
3 1 2 -8 -7 0
10
2 9 10 7 8 7 6 7 6...

output:

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

result:

ok 36398 cases.

Test #3:

score: 0
Accepted
time: 72ms
memory: 3584kb

input:

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

output:

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

result:

ok 36169 cases.

Test #4:

score: 0
Accepted
time: 86ms
memory: 3588kb

input:

36365
8
3 5 2 3 3 5 8 4
-5 -6 -1 -9 -8 -5 -7 -8
3
1 2 2
-7 -5 -4
5
2 3 1 2 4
-6 -10 -5 -3 -10
2
2 2
-9 -8
7
7 3 3 2 6 5 6
-7 -7 -10 -7 -7 -10 -4
7
6 2 4 6 5 2 5
-9 -8 -10 -1 -6 -3 -6
8
7 4 8 4 6 7 1 6
-4 -4 -6 -4 -4 -10 -6 -2
10
3 6 1 1 4 1 2 8 6 1
-5 -9 -9 -5 -10 -1 -5 -5 -1 -4
4
2 2 3 3
-7 -4 -1 -...

output:

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

result:

ok 36365 cases.

Test #5:

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

input:

6663
19
16 11 18 18 10 17 15 8 9 14 19 2 14 18 17 19 3 17 14
10 9 5 -2 3 -7 2 6 -2 5 -4 3 -6 9 6 7 4 0 -7
41
21 18 26 20 37 38 31 37 12 8 17 2 27 4 39 26 9 32 40 12 2 35 1 31 36 28 41 9 25 1 11 21 30 37 31 36 6 4 21 34 33
-3 0 -9 4 9 5 0 -2 -10 -3 -3 8 -6 7 -7 9 0 3 -2 10 -9 1 2 3 5 -2 6 7 6 -6 -2 5...

output:

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

result:

ok 6663 cases.

Test #6:

score: 0
Accepted
time: 135ms
memory: 3660kb

input:

1343
130
55 112 18 93 56 43 35 39 76 130 10 57 65 9 9 40 19 24 73 119 68 122 74 61 125 48 69 112 79 93 33 113 50 34 58 123 15 85 58 102 130 129 69 9 10 23 103 8 50 105 105 95 47 35 31 78 130 100 34 79 114 50 109 23 49 35 28 32 107 75 45 18 10 62 110 111 56 28 48 70 91 1 50 100 53 58 70 22 7 46 95 12...

output:

60
116 104 15 100 64 78 31 16 90 97 12 27 80 70 29 91 51 98 105 42 21 118 11 108 120 55 7 94 26 33 39 43 123 9 109 117 103 61 22 10 95 48 92 17 18 68 66 71 79 85 86 87 23 115 81 40 76 20 125 41
85
16 23 63 153 135 13 30 171 39 121 37 182 139 113 67 157 118 31 87 158 64 95 120 97 152 6 33 15 75 72 13...

result:

ok 1343 cases.

Test #7:

score: 0
Accepted
time: 653ms
memory: 4068kb

input:

137
1888
459 530 933 1784 1671 1327 610 1409 580 1014 1261 1770 34 1663 97 53 244 1144 298 26 706 34 1226 1667 1832 1488 247 1710 1109 267 1435 1262 1869 1872 1267 10 264 911 433 797 1841 590 250 468 1415 1573 457 1747 1343 480 1162 784 1664 1664 1888 374 453 282 1567 516 1855 1814 562 1004 785 1073...

output:

939
494 1432 36 700 327 1261 1167 1456 16 497 1268 633 883 1069 1625 300 1682 526 103 1126 244 1650 798 860 1334 253 815 1550 774 842 577 1249 1864 30 736 889 1763 778 19 372 1705 1731 1278 1002 781 1192 1321 1796 1576 1477 767 1375 415 656 1350 1169 156 662 473 1071 1295 1492 849 728 1706 1755 1545...

result:

ok 137 cases.

Test #8:

score: 0
Accepted
time: 643ms
memory: 3876kb

input:

133
1989
1728 1930 1845 787 894 1256 1355 1168 1599 1057 1253 1519 1665 638 540 1269 1704 206 571 458 952 1901 1874 937 147 1016 446 1179 503 904 1800 1607 558 1430 1286 1084 735 690 1770 251 910 187 1427 833 244 280 328 1528 1194 1484 598 421 815 49 1907 1651 1821 924 809 1632 1167 1129 440 476 192...

output:

1989
1517 382 1162 953 1950 882 1897 1038 1259 1151 659 500 1154 907 1546 992 161 989 463 1624 1148 1752 695 1588 1564 654 1180 1700 1002 939 737 1032 153 669 1712 1061 300 1437 158 1770 1096 277 591 993 1587 251 1666 560 1566 425 886 476 1146 144 1057 1525 105 1941 1585 1988 204 1509 210 791 1486 4...

result:

ok 133 cases.

Test #9:

score: 0
Accepted
time: 641ms
memory: 3964kb

input:

134
1470
823 453 281 76 908 347 944 990 913 585 648 660 991 219 646 422 846 1320 606 541 1324 1454 1152 1032 32 1364 459 879 60 652 1249 476 698 880 762 1098 1413 474 707 1200 935 594 1203 172 179 746 1224 83 259 1 337 431 505 407 1308 763 762 709 169 340 363 1075 845 890 82 322 1270 1044 781 851 90...

output:

920
400 632 159 1249 1423 622 842 1102 885 1202 120 1159 754 636 1009 605 1274 791 894 872 1181 25 1270 873 1374 770 1050 644 369 122 416 1320 1383 688 1312 571 29 1452 272 1146 379 477 1113 695 553 4 1434 84 160 65 805 1228 596 1183 886 991 105 988 1148 942 536 578 1271 760 463 745 1386 203 599 140...

result:

ok 134 cases.

Test #10:

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

input:

133
1190
251 1086 819 1186 473 671 186 1112 685 40 436 817 1185 359 278 961 818 304 706 428 448 1013 82 1102 433 706 824 895 601 869 850 859 283 840 929 200 706 821 968 418 1003 902 1108 964 130 257 984 576 923 190 916 5 955 192 128 796 899 358 860 925 1143 122 873 83 824 1183 877 401 285 546 364 40...

output:

3
180 261 750
3
166 790 962
3
868 1583 954
3
153 1313 134
3
743 1351 1293
3
209 236 553
3
1224 1549 1587
3
105 831 528
3
657 256 1200
3
1837 198 160
3
138 553 861
3
949 577 930
3
915 722 272
3
368 1178 425
3
235 951 100
3
389 133 1062
3
487 1025 585
3
74 256 630
3
107 433 236
3
197 699 708
3
1304 12...

result:

ok 133 cases.

Test #11:

score: 0
Accepted
time: 641ms
memory: 3960kb

input:

134
1672
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

828
574 1120 342 1245 332 1381 920 1567 722 1213 413 1585 664 1413 180 1534 394 1127 523 1039 419 1379 262 1626 505 1371 4 1515 817 1299 64 1370 563 1244 569 1295 603 1173 35 1409 450 1337 714 1136 119 1440 677 1238 361 1327 140 1474 455 1313 530 1093 751 1664 776 1226 566 1443 279 1589 48 992 599 1...

result:

ok 134 cases.

Test #12:

score: -100
Time Limit Exceeded

input:

12
18055
16797 6461 5661 258 15361 9217 9880 14473 16352 214 57 8242 16295 4901 8533 17041 13453 14844 17977 8109 17068 8678 7580 1720 1113 1718 10508 15915 2063 9193 3138 724 17043 15873 3164 4858 4654 7380 8811 8952 15967 9649 3576 9425 5004 9380 11990 8967 17597 16447 4348 13906 3299 7178 12969 1...

output:

8961
10146 10498 14825 14454 7450 13423 13848 9162 4955 16516 16852 1059 2191 14068 3731 17663 12850 17065 6275 10145 3183 17425 14732 7778 2768 8276 2281 2634 825 10130 5817 16247 13214 15684 2822 6512 16130 11525 6154 14353 1415 17546 4017 8331 8482 12356 7882 17109 5603 8559 4773 2389 9827 11332 ...

result: