QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#51110#1282. Necklaceckiseki#AC ✓136ms38040kbC++5.6kb2022-09-30 20:36:332022-09-30 20:36:34

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 20:36:34]
  • 评测
  • 测评结果:AC
  • 用时:136ms
  • 内存:38040kb
  • [2022-09-30 20:36:33]
  • 提交

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];
            }
        }
        
        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;
                }
                psm[j + 1].first += vi[j].first;
                psm[j + 1].second ++;
            }
        }
        for (int i = 1; i <= n; ++i) {
            psm[i].first += psm[i - 1].first;
            psm[i].second += psm[i - 1].second;
        }

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

        for (int i = 0; i < n; ++i) {

            int cp = 0;
            auto get_k = [&nsm, &np, &nps, i, &cp](int k) {
                if (nsm.size() - np[i].size() < k) return -INF;
                int needp = k - 1 + cp;
                while (cp < int(np[i].size()) and needp >= np[i][cp]) {
                    cp++;
                    needp = k - 1 + cp;
                }
                auto r = nsm[needp].first;
                if (cp > 0) r -= nps[i][cp - 1];
                return r;
            };


            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(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: 3640kb

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: 90ms
memory: 3580kb

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: 76ms
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: 82ms
memory: 3680kb

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: 74ms
memory: 3724kb

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: 84ms
memory: 3808kb

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: 83ms
memory: 4132kb

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: 60ms
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: 53ms
memory: 3864kb

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: 71ms
memory: 3984kb

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: 72ms
memory: 4012kb

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: 0
Accepted
time: 93ms
memory: 6844kb

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:

ok 12 cases.

Test #13:

score: 0
Accepted
time: 65ms
memory: 6240kb

input:

14
17434
9548 3285 2124 13465 5769 15776 17003 212 10049 15889 16817 4989 14153 13830 13062 3670 4025 3284 15928 617 3990 1450 16869 731 1918 10375 9806 12155 11182 847 8356 3496 3746 8923 11735 12340 10439 9343 2388 10754 3015 10844 4555 4572 15134 9060 9591 4313 4873 10529 16805 9835 11013 5647 15...

output:

17434
5865 5653 16808 4509 1377 14876 12450 2954 16216 15616 17207 6530 14538 8406 8752 1437 15323 2074 4047 3015 14141 7239 1348 15025 14273 3845 7586 9624 14158 10666 15730 6394 11743 16203 14477 6732 13877 11006 2008 2753 109 13602 1224 14667 5915 16104 1305 13953 8640 3889 9258 7352 4788 862 722...

result:

ok 14 cases.

Test #14:

score: 0
Accepted
time: 64ms
memory: 6292kb

input:

12
14655
11411 161 1024 7539 13177 6370 4724 10192 11161 7719 10455 11482 5760 3288 14566 7833 8877 10020 10600 808 3418 4532 587 10094 615 7241 1377 10067 960 10186 4614 1777 7424 8565 1745 6102 10828 11771 4154 13404 7074 8342 3613 363 13116 1831 1796 13398 3046 1879 10337 6921 2467 4112 5735 1220...

output:

9263
3878 14588 8231 13942 1221 10082 3210 8919 11177 1993 5731 11867 12116 632 7239 8077 8440 13913 3975 9810 10845 12569 8584 13963 1709 7196 10534 10122 6073 8030 11893 12851 13774 8532 10231 13784 12814 5695 10439 13808 13220 2240 6654 153 6932 2371 10591 3208 7446 13416 2940 11038 12468 11329 5...

result:

ok 12 cases.

Test #15:

score: 0
Accepted
time: 92ms
memory: 7496kb

input:

14
14034
10803 1737 4691 2728 3742 3502 3140 4884 11294 1581 10643 13426 7023 13376 7237 12200 1462 12551 12040 524 11824 7685 4122 4225 9127 9188 709 6498 9670 554 13326 10381 7789 4277 12503 6045 4994 6543 8010 13513 1135 5044 13759 388 6604 1461 11927 7152 10411 2045 5304 13655 5103 12866 3144 12...

output:

3
5776 8444 13704
3
10573 14255 1002
3
3139 8770 10122
3
5579 9494 1420
3
14409 6078 1901
3
8034 6393 12504
3
808 2254 5701
3
1063 4605 2517
3
2725 4334 8579
3
16013 11907 10153
3
12895 1002 7044
3
13696 4820 8058
3
13562 14861 17497
3
9192 1145 2857

result:

ok 14 cases.

Test #16:

score: 0
Accepted
time: 70ms
memory: 6920kb

input:

12
11255
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

5686
5846 9291 5418 9105 4130 10917 1685 6921 6110 6786 6078 9451 2903 10309 3604 8379 4602 6567 3860 10465 4322 9016 5850 9135 4967 10902 1283 10577 2013 7753 861 6565 183 10366 5428 10378 2241 9935 6314 9247 1372 8785 1114 9383 5520 7675 825 8384 524 9108 5916 6988 2692 8145 814 10823 4633 9329 55...

result:

ok 12 cases.

Test #17:

score: 0
Accepted
time: 117ms
memory: 19264kb

input:

3
58721
24434 9260 24075 48000 15976 20173 35443 51833 19066 41037 54110 1481 19903 51532 3423 31435 3508 11994 15714 163 55971 31702 36494 4158 51738 44184 24638 56542 45429 9219 45527 15074 28047 37930 45584 56610 49878 37478 38487 34277 34534 20191 11345 52669 4052 58673 1053 27733 28790 52960 35...

output:

29420
12053 5490 18937 1910 45889 47838 7048 6920 2532 53890 4373 42953 21402 58696 11541 31302 26341 58281 29842 7810 43028 46361 48661 25761 21342 10408 33938 700 45494 446 43244 54466 31144 30726 7317 6548 22312 716 46382 44122 33727 30831 50248 16871 46933 29341 44608 4932 788 36986 6034 9508 39...

result:

ok 3 cases.

Test #18:

score: 0
Accepted
time: 136ms
memory: 17904kb

input:

2
77676
27968 75961 21244 54489 71767 46141 53503 13873 18582 11076 64477 51679 6938 36146 38280 58457 28777 38269 14895 25463 52274 57117 4973 40172 6470 60885 61948 14050 909 60043 4187 52377 43750 1600 31546 6977 53526 11677 24682 72371 5910 18647 65163 16777 73668 26432 10296 39627 23007 71448 1...

output:

38748
6152 30779 49212 52941 8464 72561 34297 22024 16186 30885 32702 65690 56359 46062 53165 24178 29595 66291 20656 60146 52461 56934 32989 11979 7541 34847 47110 35657 52015 22366 55539 63605 22667 61971 69305 29070 29254 39017 31371 24479 10620 25563 37352 6258 2455 40118 60066 68467 27649 43719...

result:

ok 2 cases.

Test #19:

score: 0
Accepted
time: 130ms
memory: 37956kb

input:

1
200000
84638 180660 96676 145207 33392 79870 171900 125536 96004 63088 55821 129766 161448 131134 107191 45727 177392 29632 142432 198535 92403 141810 68401 132218 189131 53237 157976 172219 186777 173068 5956 125297 154368 15264 18156 9572 126885 111293 89928 31940 95413 63059 80790 20899 106847 ...

output:

99872
2791 44825 194239 182348 106207 69548 137450 189090 146945 77665 112094 108870 79611 183871 92565 133848 57682 6949 182334 57781 35786 162427 180556 5638 177939 174802 44066 159055 106103 76145 57956 179506 20457 52671 22917 148886 59732 140404 121969 51218 74820 6447 146408 29360 90455 61714 ...

result:

ok 1 cases.

Test #20:

score: 0
Accepted
time: 127ms
memory: 38040kb

input:

1
200000
778 193918 126153 94460 79465 19149 155888 59691 186 123527 158668 162560 163689 134161 155108 117642 81846 27650 15185 86475 183284 82023 110081 78779 107852 147458 182837 86532 62456 92294 124739 67588 130504 17373 180052 77006 156960 98530 80039 48041 89336 28839 47948 187599 100635 2993...

output:

99338
54868 82433 112753 34121 18181 54886 68093 7825 59365 18852 151480 183695 165293 3750 54489 191500 40171 40028 184061 69059 52344 72452 119968 109980 69740 139084 5350 22890 25068 164765 114970 107428 163131 5858 140163 194048 137745 110831 42986 108968 164771 38630 146542 147503 66129 98941 1...

result:

ok 1 cases.

Test #21:

score: 0
Accepted
time: 115ms
memory: 37996kb

input:

1
200000
149623 174471 188335 19522 182434 191133 139876 193846 104368 151263 151116 138458 157418 95972 3025 198068 129404 25668 79426 182928 131062 132637 184464 192636 18060 8975 7698 176652 162326 11520 35009 177175 73936 19482 183164 111736 154331 85768 13254 121038 74746 3132 182403 145788 859...

output:

100222
55350 29149 131215 43924 142901 117985 193757 70796 93592 14640 71857 157063 101190 133970 123351 138838 175564 26575 25510 100256 157353 56017 174294 128407 170102 16531 44307 170590 148253 76266 106285 183248 123605 176482 44331 154165 69721 164206 31732 182535 179502 56443 78368 10613 2807...

result:

ok 1 cases.

Test #22:

score: 0
Accepted
time: 122ms
memory: 38020kb

input:

1
200000
98467 179217 17812 1480 61210 20012 123864 160706 8550 20215 78155 138548 159660 98999 50942 69983 33858 56390 9075 46676 78840 40146 50335 139197 128268 103196 89455 58260 62196 154939 88383 62570 50073 54294 145060 170657 184406 48814 170660 104434 68669 168913 141049 136681 79698 96616 1...

output:

100247
42467 55477 14654 134798 167609 125386 120858 185418 29527 116855 91397 27468 19946 105700 161010 50906 89694 191982 179166 81643 118355 125744 12064 180063 118942 88462 141487 143208 170606 149950 134703 196772 12122 196356 69612 177561 105499 21683 181149 33042 11836 64621 170280 154292 144...

result:

ok 1 cases.

Test #23:

score: 0
Accepted
time: 77ms
memory: 34120kb

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:

118792
111712 151193 29619 145391 33018 155592 36783 143043 74448 140127 23580 145892 101600 149755 18478 125471 108249 135290 49620 138056 106750 196327 15475 139932 115393 141517 68903 189581 32022 141168 1206 144537 117239 163826 33856 148739 84519 181996 79128 149834 52780 154314 118433 186845 3...

result:

ok 1 cases.

Test #24:

score: 0
Accepted
time: 96ms
memory: 34764kb

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:

123120
27637 155220 14954 159496 25225 148561 40993 157686 2688 187435 57831 158974 51897 183018 67367 141884 1350 122098 41698 121031 116642 133243 106095 143373 98154 143091 30589 127935 49629 186021 55675 129647 83098 150290 107454 193239 94517 127496 8042 182724 75387 118112 47769 154339 38819 1...

result:

ok 1 cases.

Test #25:

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

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:

129882
1160 136435 477 127829 41881 124720 48095 150200 30738 110192 85922 132357 33223 114792 69622 132689 33823 130726 42648 105259 69051 110268 42929 158540 93800 146712 27926 156810 73884 124150 100791 164316 16538 163902 47971 122039 16054 118154 16502 123301 71904 128427 97985 122719 65671 136...

result:

ok 1 cases.

Test #26:

score: 0
Accepted
time: 107ms
memory: 35700kb

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:

129428
31376 140521 38214 123608 53187 107667 87023 190980 51263 125462 13924 134915 53378 141904 40185 120292 17332 182266 16338 145249 84137 195811 71016 129374 45837 173762 76991 169205 81842 146350 79145 144723 53751 130122 79819 197460 30483 103938 11739 116088 65279 169749 15930 132530 68240 1...

result:

ok 1 cases.