QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130691#2789. SortingQwerty1232#8 2ms3940kbC++202.4kb2023-07-24 19:50:072024-07-04 00:55:23

Judging History

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

  • [2024-07-04 00:55:23]
  • 评测
  • 测评结果：8
  • 用时：2ms
  • 内存：3940kb
查看
  • [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:07]
  • 提交

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 < 1e4; 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: 1ms
memory: 3768kb

input:

1
0
1
0 0

output:

1
0 0

result:

ok correct

Test #2:

score: 8
Accepted
time: 1ms
memory: 3864kb

input:

2
0 1
4
0 0
0 0
0 0
0 0

output:

4
1 1
0 0
1 1
0 0

result:

ok correct

Test #3:

score: 8
Accepted
time: 1ms
memory: 3716kb

input:

2
1 0
4
0 0
0 0
0 0
0 0

output:

4
1 1
0 1
1 1
0 0

result:

ok correct

Test #4:

score: 8
Accepted
time: 1ms
memory: 3908kb

input:

3
1 0 2
9
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

9
0 0
2 2
2 2
1 0
0 0
1 1
0 0
2 2
2 2

result:

ok correct

Test #5:

score: 8
Accepted
time: 0ms
memory: 3776kb

input:

4
3 2 0 1
16
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

16
2 2
1 1
3 3
0 0
2 3
1 2
3 3
3 3
0 0
3 0
3 3
1 1
3 3
2 2
2 2
1 1

result:

ok correct

Test #6:

score: 8
Accepted
time: 2ms
memory: 3940kb

input:

5
1 4 2 3 0
25
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

20
3 3
1 1
0 0
3 3
1 1
4 1
4 4
2 2
4 4
4 4
4 4
2 2
2 2
0 1
2 2
2 2
2 2
2 2
3 3
0 0

result:

ok correct

Test #7:

score: 8
Accepted
time: 2ms
memory: 3712kb

input:

5
4 2 1 0 3
25
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

20
3 3
1 1
0 0
3 3
1 1
1 1
4 4
2 2
4 4
3 4
4 4
2 2
2 1
3 3
2 2
2 2
0 4
2 2
3 3
0 0

result:

ok correct

Subtask #2:

score: 0
Time Limit Exceeded

Test #8:

score: 12
Accepted
time: 1ms
memory: 3712kb

input:

1
0
30
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

4
0 0
0 0
0 0
0 0

result:

ok correct

Test #9:

score: 12
Accepted
time: 2ms
memory: 3648kb

input:

2
0 1
60
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

8
1 1
1 1
0 0
0 0
1 1
0 0
1 1
1 1

result:

ok correct

Test #10:

score: 0
Time Limit Exceeded

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:

Unauthorized output

result:

Subtask #3:

score: 0
Time Limit Exceeded

Test #13:

score: 16
Accepted
time: 1ms
memory: 3648kb

input:

2
0 1
60
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1

output:

8
1 1
1 1
0 0
0 0
1 1
0 0
1 1
1 1

result:

ok correct

Test #14:

score: 16
Accepted
time: 2ms
memory: 3652kb

input:

5
0 4 1 3 2
150
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
...

output:

20
3 3
1 1
0 0
3 3
1 1
1 1
4 4
2 2
4 4
4 4
4 4
2 2
2 4
3 3
2 2
2 2
2 2
1 4
3 3
0 0

result:

ok correct

Test #15:

score: 0
Time Limit Exceeded

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:

Unauthorized output

result:

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

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

result:

Subtask #6:

score: 0
Skipped

Dependency #5:

0%
English 繁體中文 简体中文

服务器时间: 2024-11-29 23:27:52 | 开源项目