oj.uz

Submission #167388

# Submission time Handle Problem Language Result Execution time Memory
167388 2019-12-07T22:36:10 Z faremy Sorting (IOI15_sorting) C++14
100 / 100
 266 ms 28644 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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