QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236532#2789. SortingCamillus0 1ms3724kbC++20980b2023-11-04 01:25:072023-11-04 01:25:07

Judging History

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

  • [2023-11-04 01:25:07]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：3724kb
查看
  • [2023-11-04 01:25:07]
  • 提交

answer

#include "bits/stdc++.h"
#include "sorting.h"
using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l = -1, r = M;
	while (r - l > 1) {
		int m = (l + r) / 2;

		vector<int> s(S, S + N);
		for (int i = 0; i < m; i++) {
			swap(s[X[i]], s[Y[i]]);
		}

		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (i != s[i]) {
				cnt += 1;
				swap(s[i], s[s[i]]);
			}
		}

		if (cnt <= m) {
			r = m;
		} else {
			l = m;
		}
	}

	vector<int> s(S, S + N);

	vector<pair<int, int>> t;

	for (int i = 0; i < r; i++) {
		if (i != s[i]) {
			t.emplace_back(s[i], s[s[i]]);
			swap(s[i], s[s[i]]);
		}
	}

	t.resize(r, make_pair(0, 0));

	vector<int> pos(N);
	
	for (int i = 0; i < N; i++) {
		pos[s[i]] = i;
	}

	for (int i = 0; i < r; i++) {
		swap(pos[s[X[i]]], pos[s[Y[i]]]);
		swap(s[X[i]], s[Y[i]]);

		auto [x, y] = t[i];

		P[i] = pos[x];
		Q[i] = pos[y];
	}
	return r;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1
0
1
0 0

output:

0

result:

ok correct

Test #2:

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

input:

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

output:

0

result:

ok correct

Test #3:

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

input:

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

output:

1
1 0

result:

ok correct

Test #4:

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

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:

1
1 0

result:

ok correct

Test #5:

score: -8
Wrong Answer
time: 0ms
memory: 3560kb

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:

2
3 0
2 1

result:

wrong answer the final array is not sorted

Subtask #2:

score: 0
Wrong Answer

Test #8:

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

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:

0

result:

ok correct

Test #9:

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

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:

0

result:

ok correct

Test #10:

score: -12
Wrong Answer
time: 0ms
memory: 3652kb

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:

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

result:

wrong answer the final array is not sorted

Subtask #3:

score: 0
Wrong Answer

Test #13:

score: 16
Accepted
time: 0ms
memory: 3628kb

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:

0

result:

ok correct

Test #14:

score: -16
Wrong Answer
time: 0ms
memory: 3644kb

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:

2
4 0
0 0

result:

wrong answer the final array is not sorted

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Wrong Answer

Test #28:

score: 0
Wrong Answer
time: 1ms
memory: 3724kb

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:

1120
530 0
1775 1
466 2
953 39
230 753
1179 320
944 6
752 613
990 1026
1316 477
275 10
1029 11
158 12
152 13
1673 14
1706 603
172 16
115 17
599 18
1661 19
131 20
699 21
1112 1014
454 23
551 193
1059 25
291 1106
495 27
67 29
773 804
480 1062
839 32
462 33
130 34
757 35
879 955
285 37
439 38
3 39
1429...

result:

wrong answer the final array is not sorted

Subtask #6:

score: 0
Skipped

Dependency #5:

0%
English 繁體中文 简体中文

Server Time: 2024-11-29 23:48:35 | OpenSource Project