Submission #426016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426016	2021-06-13T13:00:24 Z	_fractal	Sorting (IOI15_sorting)	C++14	20 / 100	128 ms	356 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;
				}
			}
			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;
			}
		}
		bool f = 1;
		for (int i = 1; i < N; ++i)
			if (S[i - 1] > S[i])
				f = 0;
		if (F && f) {
			return r;
		}
		--M;
	}
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:31:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
   31 |    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	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 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	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 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	1 ms	224 KB	Output is correct
10	Correct	128 ms	204 KB	Output is correct
11	Correct	128 ms	304 KB	Output is correct
12	Correct	123 ms	324 KB	Output is correct

Subtask #3

0 / 16.0

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

Subtask #4

0 / 18.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	0 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	1 ms	224 KB	Output is correct
10	Correct	128 ms	204 KB	Output is correct
11	Correct	128 ms	304 KB	Output is correct
12	Correct	123 ms	324 KB	Output is correct
13	Incorrect	1 ms	204 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

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

Subtask #6

0 / 26.0

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