답안 #167388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167388	2019-12-07T22:36:10 Z	faremy	정렬하기 (IOI15_sorting)	C++14	100 / 100	266 ms	28644 KB

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[X[requiredSwaps]], perm[Y[requiredSwaps]]);
		std::swap(reversePerm[perm[X[requiredSwaps]]], reversePerm[perm[Y[requiredSwaps]]]);
	}

	return answer;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	404 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	6 ms	376 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	404 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	252 KB	Output is correct
21	Correct	3 ms	504 KB	Output is correct
22	Correct	3 ms	632 KB	Output is correct
23	Correct	3 ms	504 KB	Output is correct
24	Correct	3 ms	504 KB	Output is correct
25	Correct	3 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	3 ms	504 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	760 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	432 KB	Output is correct
5	Correct	4 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	3 ms	504 KB	Output is correct
8	Correct	3 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	632 KB	Output is correct
13	Correct	3 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	3 ms	760 KB	Output is correct
3	Correct	3 ms	504 KB	Output is correct
4	Correct	2 ms	432 KB	Output is correct
5	Correct	4 ms	504 KB	Output is correct
6	Correct	2 ms	504 KB	Output is correct
7	Correct	3 ms	504 KB	Output is correct
8	Correct	3 ms	632 KB	Output is correct
9	Correct	3 ms	632 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	632 KB	Output is correct
13	Correct	3 ms	504 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	203 ms	22116 KB	Output is correct
16	Correct	211 ms	24692 KB	Output is correct
17	Correct	235 ms	24164 KB	Output is correct
18	Correct	80 ms	16760 KB	Output is correct
19	Correct	177 ms	20716 KB	Output is correct
20	Correct	181 ms	20716 KB	Output is correct
21	Correct	183 ms	21692 KB	Output is correct
22	Correct	195 ms	18788 KB	Output is correct
23	Correct	225 ms	25960 KB	Output is correct
24	Correct	240 ms	25828 KB	Output is correct
25	Correct	241 ms	24164 KB	Output is correct
26	Correct	174 ms	19744 KB	Output is correct
27	Correct	189 ms	18924 KB	Output is correct
28	Correct	243 ms	26468 KB	Output is correct
29	Correct	220 ms	20836 KB	Output is correct
30	Correct	115 ms	18112 KB	Output is correct
31	Correct	210 ms	21220 KB	Output is correct
32	Correct	235 ms	25316 KB	Output is correct
33	Correct	249 ms	24676 KB	Output is correct
34	Correct	222 ms	21864 KB	Output is correct
35	Correct	181 ms	20204 KB	Output is correct
36	Correct	62 ms	16120 KB	Output is correct
37	Correct	266 ms	28644 KB	Output is correct
38	Correct	234 ms	27484 KB	Output is correct
39	Correct	245 ms	27620 KB	Output is correct

답안 #167388

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0