제출 #1028828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1028828		aykhn	정렬하기 (IOI15_sorting)	C++17	74 / 100	1044 ms	14832 KiB

sorting

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

using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) 
{
	int l = 0, r = M;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		int p[N];
		iota(p, p + N, 0);
		for (int i = 0; i < mid; i++) swap(p[X[i]], p[Y[i]]);
		int ind[N], cur[N];
		for (int i = 0; i < N; i++) ind[i] = i, cur[i] = S[i];
		for (int i = 0; i < mid; i++) 
		{
			swap(ind[X[i]], ind[Y[i]]);
			swap(cur[X[i]], cur[Y[i]]);
			int f1 = -1, f2 = -1;
			for (int j = 0; j < N; j++)
			{
				if (ind[j] != p[cur[j]])
				{
					f1 = j;
					for (int k = 0; k < N; k++)
					{
						if (ind[k] == p[cur[j]]) 
						{
							f2 = k;
							break;
						}
					}
					break;
				}
			}
			if (f1 != -1) swap(cur[f1], cur[f2]);
		}
		int ok = 1;
		for (int i = 0; i < N; i++)
		{
			if (ind[i] != p[cur[i]]) ok = 0;
		}
		if (ok) r = mid;
		else l = mid + 1;
	}
	int p[N];
	iota(p, p + N, 0);
	for (int i = 0; i < l; i++) swap(p[X[i]], p[Y[i]]);
	int ind[N], cur[N];
	for (int i = 0; i < N; i++) ind[i] = i, cur[i] = S[i];
	for (int i = 0; i < l; i++) 
	{
		swap(ind[X[i]], ind[Y[i]]);
		swap(cur[X[i]], cur[Y[i]]);
		int f1 = -1, f2 = -1;
		for (int j = 0; j < N; j++)
		{
			if (ind[j] != p[cur[j]])
			{
				f1 = j;
				for (int k = 0; k < N; k++)
				{
					if (ind[k] == p[cur[j]]) 
					{
						f2 = k;
						break;
					}
				}
				break;
			}
		}
		if (f1 != -1) 
		{
			P[i] = f1, Q[i] = f2;
			swap(cur[f1], cur[f2]);
		}
		else P[i] = Q[i] = 0;
	}
	return l;
}

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