Submission #100961

#	Time	Username	Problem	Language	Result	Execution time	Memory
100961		luciocf	Sorting (IOI15_sorting)	C++14	100 / 100	614 ms	24184 KiB

sorting

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

using namespace std;

const int maxn = 2e5+10;
const int maxm = 6e5+10;

typedef pair<int, int> pii;

int s[maxn], final[maxn], pos[maxn], pos_final[maxn];

// checa se S está ordenado
bool check(int N)
{
	for (int i = 0; i < N; i++)
		if (s[i] != i) return false;

	return true;
}

// Faz a operação de trocar os índices
void replace(int i, int j, bool q)
{
	int a, b;
	
	if (q)
	{
		a = s[i], b = s[j];

		s[i] = b, s[j] = a;

		pos[a] = j, pos[b] = i;
	}
	else
	{
		a = final[i], b = final[j];

		final[i] = b, final[j] = a;

		pos_final[a] = j, pos_final[b] = i;
	}
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{	
	for (int i = 0; i < N; i++)
		final[i] = s[i] = S[i], pos_final[s[i]] = pos[s[i]] = i;

	if (check(N)) return 0;

	int ini = 1, fim = N+1, ans = N+1;

	vector<int> curP(M), curQ(M);

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		for (int i = 0; i < N; i++)
			final[i] = s[i] = S[i], pos_final[s[i]] = pos[s[i]] = i;

		for (int i = 0; i < mid; i++)
			replace(X[i], Y[i], 0);

		int first = 0;
		for (int j = 0; j < mid; j++)
		{
			replace(X[j], Y[j], 1);

			for (int i = first; i < N; i++)
			{
				if (final[i] == i)
				{
					first++;
					curP[j] = curQ[j] = 0;
					continue;
				}

				curP[j] = pos[i], curQ[j] = pos[final[i]];
				replace(curP[j], curQ[j], 1);
				replace(pos_final[i], i, 0);

				first++;

				break;
			}
		}

		if (check(N))
		{
			fim = mid-1, ans = mid;
			for (int i = 0; i < ans; i++)
				P[i] = curP[i], Q[i] = curQ[i];
		}
		else ini = mid+1;
	}
	
	return ans;
}

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