oj.uz

답안 #426028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426028 2021-06-13T13:05:07 Z _fractal 정렬하기 (IOI15_sorting) C++14
20 / 100
 146 ms 392 KB 
#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 = 0; i < M; ++i)
			P[i] = Q[i] = 0;
		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]]);
			bool f = 1;
			for (int j = 1; j < N; ++j)
				if (S[j - 1] > S[j])
					f = 0;
			if (f && i + 1 != M) {
				F = 0;
				break;
			}
			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 && f) {
			return r;
		}
		--M;
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 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 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 204 KB Output is correct
10 Correct 132 ms 204 KB Output is correct
11 Correct 146 ms 332 KB Output is correct
12 Correct 126 ms 308 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 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 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 204 KB Output is correct
10 Correct 132 ms 204 KB Output is correct
11 Correct 146 ms 332 KB Output is correct
12 Correct 126 ms 308 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 392 KB Output isn't correct
2 Halted 0 ms 0 KB -