Submission #532753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
532753	2022-03-03T20:16:38 Z	sliviu	Sorting (IOI15_sorting)	C++17	100 / 100	176 ms	21684 KB

sorting

#include <bits/stdc++.h>

using namespace std;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int s1[], int s2[]) {
	vector<int> p(n);
	for (int i = 0; i < n; ++i)
		p[i] = s[i];
	int okk = 1;
	for (int i = 0; i < n; ++i)
		if (p[i] != i)
			okk = 0;
	if (okk)
		return 0;
	int left = 0, right = n - 1;
	auto ok = [&](int pos) {
		auto p_ = p;
		for (int i = 0; i <= pos; ++i)
			swap(p_[x[i]], p_[y[i]]);
		int ans = n;
		vector<int> seen(n);
		for (int i = 0; i < n; ++i)
			if (!seen[i]) {
				--ans;
				seen[i] = 1;
				for (int j = p_[i]; j != i; j = p_[j])
					seen[j] = 1;
			}
		return ans <= pos + 1;
	};
	while (left < right) {
		int m = (left + right) / 2;
		if (ok(m))
			right = m;
		else
			left = m + 1;
	}
	auto p_ = p;
	for (int i = 0; i <= left; ++i)
		swap(p_[x[i]], p_[y[i]]);
	int cur = 0;
	vector<int> seen(n), inv(n);
	for (int i = 0; i < n; ++i)
		if (!seen[i] && p_[i] != i) {
			vector<int> sol = {i};
			for (int j = p_[i]; j != i; j = p_[j])
				sol.emplace_back(j), seen[j] = 1;
			for (int i = 0; i < (int)sol.size() - 1; ++i)
				s1[cur] = sol[i], s2[cur++] = sol[i + 1];
		}
	for (int i = 0; i < n; ++i)
		inv[p[i]] = i;
	for (int i = 0; i <= left; ++i) {
		swap(inv[p[x[i]]], inv[p[y[i]]]);
		swap(p[x[i]], p[y[i]]);
		s1[i] = inv[s1[i]], s2[i] = inv[s2[i]];
		swap(inv[p[s1[i]]], inv[p[s2[i]]]);
		swap(p[s1[i]], p[s2[i]]);
	}
	return left + 1;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:32:7: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   32 |   int m = (left + right) / 2;
      |       ^
sorting.cpp:5:39: note: shadowed declaration is here
    5 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int s1[], int s2[]) {
      |                                   ~~~~^
sorting.cpp:48:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   48 |    for (int i = 0; i < (int)sol.size() - 1; ++i)
      |             ^
sorting.cpp:43:11: note: shadowed declaration is here
   43 |  for (int i = 0; i < n; ++i)
      |           ^
sorting.cpp:5:39: warning: unused parameter 'm' [-Wunused-parameter]
    5 | int findSwapPairs(int n, int s[], int m, int x[], int y[], int s1[], int s2[]) {
      |                                   ~~~~^

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	300 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct

Subtask #4
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	292 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	300 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	1 ms	204 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	204 KB	Output is correct
21	Correct	1 ms	460 KB	Output is correct
22	Correct	1 ms	460 KB	Output is correct
23	Correct	1 ms	432 KB	Output is correct
24	Correct	1 ms	460 KB	Output is correct
25	Correct	1 ms	428 KB	Output is correct
26	Correct	1 ms	460 KB	Output is correct
27	Correct	1 ms	460 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	2 ms	464 KB	Output is correct
8	Correct	2 ms	464 KB	Output is correct
9	Correct	2 ms	464 KB	Output is correct
10	Correct	1 ms	464 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	1 ms	464 KB	Output is correct
13	Correct	1 ms	464 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct

Subtask #6
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	2 ms	464 KB	Output is correct
8	Correct	2 ms	464 KB	Output is correct
9	Correct	2 ms	464 KB	Output is correct
10	Correct	1 ms	464 KB	Output is correct
11	Correct	1 ms	464 KB	Output is correct
12	Correct	1 ms	464 KB	Output is correct
13	Correct	1 ms	464 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	139 ms	18792 KB	Output is correct
16	Correct	143 ms	20016 KB	Output is correct
17	Correct	176 ms	20828 KB	Output is correct
18	Correct	42 ms	14020 KB	Output is correct
19	Correct	135 ms	18364 KB	Output is correct
20	Correct	149 ms	18936 KB	Output is correct
21	Correct	145 ms	19048 KB	Output is correct
22	Correct	129 ms	16176 KB	Output is correct
23	Correct	145 ms	21684 KB	Output is correct
24	Correct	162 ms	21356 KB	Output is correct
25	Correct	162 ms	20988 KB	Output is correct
26	Correct	151 ms	19016 KB	Output is correct
27	Correct	124 ms	18296 KB	Output is correct
28	Correct	153 ms	21284 KB	Output is correct
29	Correct	161 ms	19736 KB	Output is correct
30	Correct	97 ms	17836 KB	Output is correct
31	Correct	156 ms	20252 KB	Output is correct
32	Correct	151 ms	20840 KB	Output is correct
33	Correct	161 ms	20920 KB	Output is correct
34	Correct	162 ms	20360 KB	Output is correct
35	Correct	130 ms	18172 KB	Output is correct
36	Correct	55 ms	17400 KB	Output is correct
37	Correct	170 ms	21540 KB	Output is correct
38	Correct	164 ms	21056 KB	Output is correct
39	Correct	169 ms	20584 KB	Output is correct

Submission #532753

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0