Submission #1028842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028842		aykhn	Sorting (IOI15_sorting)	C++17	74 / 100	1057 ms	23772 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], idx[N];
		for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
		set<int> s;
		for (int i = 0; i < N; i++)
		{
			if (ind[i] != p[cur[i]]) s.insert(i);
		}
		for (int i = 0; i < mid; i++) 
		{
			swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
			swap(ind[X[i]], ind[Y[i]]);
			swap(cur[X[i]], cur[Y[i]]);
			if (s.count(X[i]) && !s.count(Y[i])) 
			{
				s.erase(X[i]), s.insert(Y[i]);
			}
			else if (!s.count(X[i]) && s.count(Y[i]))
			{
				s.insert(X[i]), s.erase(Y[i]);
			}
			int f1 = -1, f2 = -1;
			if (!s.empty())
			{
				f1 = *s.begin();
				f2 = idx[p[cur[f1]]];
				s.erase(s.begin());
			}
			if (f1 != -1) 
			{
				swap(cur[f1], cur[f2]);
				if (s.count(f2)) 
				{
					s.erase(f2), s.insert(f1);
					if (ind[f1] == p[cur[f1]]) s.erase(f1);
				}
			}
		}
		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], idx[N];
	for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
	set<int> s;
	for (int i = 0; i < N; i++)
	{
		if (ind[i] != p[cur[i]]) s.insert(i);
	}
	for (int i = 0; i < l; i++) 
	{
		swap(idx[ind[X[i]]], idx[ind[Y[i]]]);
		swap(ind[X[i]], ind[Y[i]]);
		swap(cur[X[i]], cur[Y[i]]);
		if (s.count(X[i]) && !s.count(Y[i])) 
		{
			s.erase(X[i]), s.insert(Y[i]);
		}
		else if (!s.count(X[i]) && s.count(Y[i]))
		{
			s.insert(X[i]), s.erase(Y[i]);
		}
		int f1 = -1, f2 = -1;
		if (!s.empty())
		{
			f1 = *s.begin();
			f2 = idx[p[cur[f1]]];
			s.erase(s.begin());
		}
		if (f1 != -1) 
		{
			P[i] = f1, Q[i] = f2;
			swap(cur[f1], cur[f2]);
			if (s.count(f2)) 
			{
				s.erase(f2), s.insert(f1);
				if (ind[f1] == p[cur[f1]]) s.erase(f1);
			}
		}
		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