제출 #1185732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185732		Kerim	정렬하기 (IOI15_sorting)	C++20	74 / 100	1094 ms	8008 KiB

sorting

#include "sorting.h"
#include "bits/stdc++.h"

using namespace std;

int f(int r, int n, int S[], int X[], int Y[], int p[], int q[]){
	int P[n], pos[n];
	for (int i = 0; i < n; i++)
		P[i] = S[i];
	//Ermek's first R swap operations
	for (int i = 0; i < r; i++)	
		swap(P[X[i]], P[Y[i]]);
	for (int i = 0; i < n; i++)
		pos[P[i]] = i;
	int r_prime = 0;
	for (int i = 0; i < n; i++){
		if (pos[i] == i)
			continue;
		int j = pos[i];
		p[r_prime] = P[i];
		q[r_prime] = P[j];
		r_prime += 1;
		swap(pos[P[i]], pos[P[j]]);
		swap(P[i], P[j]);
	}
	return r_prime;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int r = 0;
    while (r <= M and f(r, N, S, X, Y, P, Q) > r)
		r += 1;
	int r_prime = f(r, N, S, X, Y, P, Q);
	int pos[N];
	for (int i = 0; i < N; i++)
		pos[S[i]] = i;
	for (int i = 0; i < r_prime; i++){
		swap(pos[S[X[i]]], pos[S[Y[i]]]);
		swap(S[X[i]], S[Y[i]]);
		int p = pos[P[i]], q = pos[Q[i]];
		swap(pos[S[p]], pos[S[q]]);
		swap(S[p], S[q]);
		P[i] = p;
		Q[i] = q;
	}
	for (int i = r_prime; i < r; i++)
		P[i] = Q[i] = 0;
	return r;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 0 / 26