QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#130693	#2789. Sorting	Qwerty1232^#	36	112ms	4060kb	C++20	2.4kb	2023-07-24 19:50:49	2024-07-04 00:55:26

Judging History

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

[2024-07-04 00:55:26]
评测

测评结果：36
用时：112ms
内存：4060kb

查看

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-24 19:50:49]
提交

answer

#include "sorting.h"

#include <bits/stdc++.h>

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    if (0 && std::all_of(X, X + M, [&](int a) { return a == 0; }) && std::all_of(Y, Y + M, [&](int a) { return a == 0; })) {
        std::vector<std::pair<int, int>> ans;

        std::vector<int> used(n);
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int u = i;
                do {
                    int t = S[u];
                    used[u] = true;
                    if (t != i) {
                        ans.push_back({i, t});
                    }
                    u = t;
                    assert(ans.size() < M);
                } while (u != i);
            }
        }

        for (int i = 0; i < ans.size(); i++) {
            P[i] = ans[i].first;
            Q[i] = ans[i].second;
        }
        return ans.size();
    }

    auto cum = [&](std::vector<std::pair<int, int>> ans) {
        int m = ans.size();
        std::vector<int> p(S, S + n);
        for (int i = 0; i < m; i++) {
            std::swap(p[X[i]], p[Y[i]]);
            std::swap(p[ans[i].first], p[ans[i].second]);
        }
        std::vector<bool> used(n);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                int u = i;
                do {
                    used[u] = true;
                    u = p[u];
                } while (u != i);
                cnt++;
            }
        }
        return cnt;
    };

    static std::mt19937 rnd;

    for (int iter = 0;; iter++) {
        int m = std::min(M, 4 * n);
        std::vector<std::pair<int, int>> ans(m);
        int sc = cum(ans);
        // while (sc < n) {
        for (int f = 0; f < 1e5; f++) {
            int i = rnd() % m;
            std::pair<int, int> pr = {rnd() % n, rnd() % n};
            std::swap(ans[i], pr);
            int sc2 = cum(ans);
            if (sc2 >= sc) {
                if (sc2 > sc) {
                    std::cerr << sc2 << "\n";
                }
                sc = sc2;
            } else {
                std::swap(ans[i], pr);
            }
        }

        if (sc == n) {
            for (int i = 0; i < ans.size(); i++) {
                P[i] = ans[i].first;
                Q[i] = ans[i].second;
            }
            return ans.size();
        }
    }
}

源文件, 语言: C++20

詳細信息

Subtask #1:

score: 8

Accepted

Test #1:

score: 8

Accepted

time: 6ms

memory: 3732kb

input:

output:

1
0 0

result:

ok correct

Test #2:

score: 0

Accepted

time: 3ms

memory: 3680kb

input:

output:

result:

ok correct

Test #3:

score: 0

Accepted

time: 7ms

memory: 3744kb

input:

output:

result:

ok correct

Test #4:

score: 0

Accepted

time: 6ms

memory: 3796kb

input:

output:

result:

ok correct

Test #5:

score: 0

Accepted

time: 11ms

memory: 3792kb

input:

output:

result:

ok correct

Test #6:

score: 0

Accepted

time: 12ms

memory: 3852kb

input:

output:

result:

ok correct

Test #7:

score: 0

Accepted

time: 12ms

memory: 3832kb

input:

output:

result:

ok correct

Subtask #2:

score: 12

Accepted

Test #8:

score: 12

Accepted

time: 6ms

memory: 4012kb

input:

output:

result:

ok correct

Test #9:

score: 0

Accepted

time: 8ms

memory: 3728kb

input:

output:

result:

ok correct

Test #10:

score: 0

Accepted

time: 112ms

memory: 4060kb

input:

98
82 70 31 12 27 51 84 90 66 8 49 52 74 91 46 7 96 67 63 85 34 50 87 83 58 78 26 39 77 48 2 55 94 25 61 56 53 13 32 86 72 20 37 73 9 93 65 28 18 11 71 59 88 35 76 40 24 36 33 3 17 29 38 5 21 15 79 30 62 92 45 80 64 95 43 75 97 23 16 57 22 60 41 69 0 42 14 10 47 68 19 4 1 6 44 81 54 89
2940
0 0
0 0
...

output:

result:

ok correct

Test #11:

score: 0

Accepted

time: 110ms

memory: 3864kb

input:

99
8 14 3 0 98 74 18 10 50 93 49 23 80 2 54 79 90 31 66 38 81 36 42 83 39 7 9 71 59 62 67 4 68 5 70 72 34 95 25 27 45 61 97 48 29 15 46 12 87 22 26 63 77 84 11 85 30 24 40 78 41 1 96 69 94 19 6 65 33 13 52 75 88 82 86 20 92 43 89 47 28 73 35 32 53 60 21 16 37 58 44 76 57 56 17 55 91 51 64
2970
0 0
0...

output:

result:

ok correct

Test #12:

score: 0

Accepted

time: 109ms

memory: 3872kb

input:

96
12 91 75 59 44 30 52 63 41 13 93 79 82 60 85 78 50 53 57 8 80 67 34 24 87 17 47 33 83 21 81 40 89 49 32 70 26 9 43 7 11 37 94 36 23 28 90 42 35 25 62 56 20 84 55 45 46 22 77 51 0 69 1 31 54 2 3 58 88 76 5 6 65 92 39 66 15 95 10 27 14 86 72 4 68 18 38 19 64 73 71 74 48 29 61 16
2880
0 0
0 0
0 0
0 ...

output:

result:

ok correct

Subtask #3:

score: 16

Accepted

Test #13:

score: 16

Accepted

time: 8ms

memory: 3732kb

input:

output:

result:

ok correct

Test #14:

score: 0

Accepted

time: 9ms

memory: 3728kb

input:

output:

result:

ok correct

Test #15:

score: 0

Accepted

time: 101ms

memory: 3832kb

input:

96
7 15 12 95 11 50 20 42 81 29 58 80 56 71 63 66 44 6 64 39 2 22 73 1 24 27 69 28 45 25 60 61 5 94 14 65 9 86 68 32 79 37 3 57 34 35 10 88 76 78 21 93 19 53 84 52 4 33 38 55 62 67 77 41 31 48 91 49 51 43 90 8 87 54 16 17 70 46 85 0 75 92 74 47 36 89 30 13 59 26 40 18 82 83 72 23
2880
0 1
0 1
0 1
0 ...

output:

result:

ok correct

Test #16:

score: 0

Accepted

time: 109ms

memory: 3868kb

input:

99
28 2 16 95 73 6 30 90 18 46 82 69 59 4 40 49 33 29 66 86 97 56 22 96 38 35 67 15 83 44 36 72 81 41 76 47 34 87 65 9 92 57 0 55 68 5 32 17 61 50 14 19 58 24 98 48 53 60 45 12 39 3 8 74 88 77 13 85 84 42 79 51 94 70 10 25 75 31 62 27 64 1 80 78 21 37 7 63 52 23 71 20 54 26 43 91 89 93 11
2970
0 1
0...

output:

result:

ok correct

Test #17:

score: 0

Accepted

time: 105ms

memory: 3780kb

input:

99
52 0 59 91 38 87 65 75 48 11 64 60 95 71 62 79 49 30 47 56 33 16 94 8 78 36 13 68 9 35 74 77 80 24 15 83 28 66 12 51 92 84 43 40 4 46 63 57 17 85 42 25 81 14 50 31 72 34 70 88 67 53 6 37 44 45 96 69 2 86 76 55 3 82 22 5 93 39 26 41 98 7 27 1 20 29 23 19 54 18 61 90 89 32 97 73 10 58 21
2970
0 1
0...

output:

result:

ok correct

Test #18:

score: 0

Accepted

time: 11ms

memory: 3988kb

input:

output:

result:

ok correct

Subtask #4:

score: 0

Time Limit Exceeded

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #19:

score: 18

Accepted

time: 6ms

memory: 3748kb

input:

output:

result:

ok correct

Test #20:

score: 0

Accepted

time: 8ms

memory: 3788kb

input:

output:

result:

ok correct

Test #21:

score: -18

Time Limit Exceeded

input:

481
264 22 307 266 238 227 68 26 13 12 384 162 410 306 374 311 442 38 407 310 280 308 333 146 326 381 367 110 190 33 141 468 153 393 157 415 229 75 276 392 349 348 179 445 317 64 78 20 323 257 292 395 129 259 165 398 151 219 14 116 338 188 243 61 150 84 72 340 155 133 459 464 248 433 124 399 177 62 ...

output:

Unauthorized output

result:

Subtask #5:

score: 0

Time Limit Exceeded

Test #28:

score: 0

Time Limit Exceeded

input:

1800
530 1775 466 953 230 1179 944 752 990 1316 275 1029 158 152 1673 1706 172 115 599 1661 131 699 1112 454 551 1059 291 495 28 67 773 480 839 462 1210 757 879 285 439 3 1429 820 26 1023 942 199 356 625 1705 1421 144 1529 716 7 1485 1027 1599 696 517 1353 456 1389 273 1363 1414 1177 718 41 777 1621...

output:

Unauthorized output