Submission #167386

#	Time	Username	Problem	Language	Result	Execution time	Memory
167386		faremy	Sorting (IOI15_sorting)	C++14	0 / 100	3 ms	632 KiB

sorting

#include "sorting.h"

#include <algorithm>
#include <vector>


const int MAXN = 2e5;

int perm[MAXN];
bool seen[MAXN];

std::vector<int> left;
std::vector<int> right;
int reversePerm[MAXN];


void setup(int swaps, int permSize, int initPerm[], int swapLeft[], int swapRight[])
{
	for (int iPos = 0; iPos < permSize; iPos++)
	{
		perm[iPos] = initPerm[iPos];
		seen[iPos] = false;
	}
	
	for (int iSwap = 0; iSwap < swaps; iSwap++)
		std::swap(perm[swapLeft[iSwap]], perm[swapRight[iSwap]]);
}

bool floodfill(int pos)
{
	if (seen[pos])
		return false;
	seen[pos] = true;

	floodfill(perm[pos]);
	return true;
}

int countcycles(int permSize)
{
	int cycles = 0;
	for (int iPos = 0; iPos < permSize; iPos++)
		cycles += floodfill(iPos);
	return cycles;
}

bool createpairs(int pos)
{
	if (seen[pos])
		return false;
	seen[pos] = true;

	if (createpairs(perm[pos]))
	{
		left.emplace_back(perm[pos]);
		right.emplace_back(perm[perm[pos]]);
	}

	return true;
}

int minswaps(int lower, int upper, int permSize, int initPerm[], int swapLeft[], int swapRight[])
{
	if (lower == upper)
		return upper;
	int swaps = (lower + upper) / 2;

	setup(swaps, permSize, initPerm, swapLeft, swapRight);
	if (permSize - countcycles(permSize) <= swaps)
		return minswaps(lower, swaps, permSize, initPerm, swapLeft, swapRight);
	return minswaps(swaps + 1, upper, permSize, initPerm, swapLeft, swapRight);
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
    int requiredSwaps = minswaps(0, M, N, S, X, Y);
	int answer = requiredSwaps;
	setup(requiredSwaps, N, S, X, Y);

	for (int iPos = 0; iPos < N; iPos++)
	{
		createpairs(iPos);
		reversePerm[perm[iPos]] = iPos;
	}

	while ((int)left.size() < requiredSwaps)
	{
		requiredSwaps--;
		P[requiredSwaps] = Q[requiredSwaps] = 0;
		std::swap(perm[X[requiredSwaps]], perm[Y[requiredSwaps]]);
		std::swap(reversePerm[perm[X[requiredSwaps]]], reversePerm[perm[Y[requiredSwaps]]]);
	}

	while (requiredSwaps > 0)
	{
		requiredSwaps--;
		P[requiredSwaps] = reversePerm[left[requiredSwaps]];
		Q[requiredSwaps] = reversePerm[right[requiredSwaps]];

		std::swap(perm[reversePerm[left[requiredSwaps]]], perm[reversePerm[right[requiredSwaps]]]);
		std::swap(reversePerm[left[requiredSwaps]], reversePerm[right[requiredSwaps]]);

		std::swap(perm[X[requiredSwaps]], perm[Y[requiredSwaps]]);
		std::swap(reversePerm[perm[X[requiredSwaps]]], reversePerm[perm[Y[requiredSwaps]]]);
	}

	return answer;
}

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