Submission #426011

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426011	2021-06-13T12:57:23 Z	_fractal	Sorting (IOI15_sorting)	C++14	20 / 100	124 ms	332 KB

sorting

#include "sorting.h"
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;


int findSwapPairs(int N, int SS[], int M, int X[], int Y[], int P[], int Q[]) {
	int A[N], pos[N], S[N];
	while (true) {
		bool F = 1;
		for (int i = 0; i < N; ++i)
			A[i] = i, S[i] = SS[i];
		for (int i = M - 1; i >= 0; --i)
			swap(A[X[i]], A[Y[i]]);
		int r = 0;
		for (int i = 0; i < M; ++i) {
			swap(S[X[i]], S[Y[i]]);
			swap(A[X[i]], A[Y[i]]);
			for (int j = 0; j < N; ++j)
				pos[A[j]] = j;
			for (int j = 0; j < N; ++j) {
				if (pos[S[j]] != j) {
					Q[i] = j, P[i] = pos[S[j]];
					++r;
					break;
				}
			}
			if (Q[i] == P[i])
				break;
			swap(S[Q[i]], S[P[i]]);
			bool f = 1;
			for (int i = 1; i < N; ++i)
				if (S[i - 1] > S[i])
					f = 0;
			if (f && i + 1 != M) {
				F = 0;
				break;
			}
		}
		if (F) {
			return r;
		}
		--M;
	}
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:33:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   33 |    for (int i = 1; i < N; ++i)
      |             ^
sorting.cpp:17:12: note: shadowed declaration is here
   17 |   for (int i = 0; i < M; ++i) {
      |            ^

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	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 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	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	121 ms	300 KB	Output is correct
11	Correct	124 ms	276 KB	Output is correct
12	Correct	120 ms	324 KB	Output is correct

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Incorrect	1 ms	204 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

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	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	121 ms	300 KB	Output is correct
11	Correct	124 ms	276 KB	Output is correct
12	Correct	120 ms	324 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Incorrect	1 ms	204 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	332 KB	Output isn't correct
2	Halted	0 ms	0 KB	-