Submission #1028917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028917		aykhn	Sorting (IOI15_sorting)	C++17	0 / 100	2 ms	600 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 p[N], ind[N], cur[N], idx[N], u[N];
	vector<int> s;
	int l = 0, r = M;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		s.clear();
		iota(p, p + N, 0);
		iota(u, u + N, 0);
		for (int i = 0; i < mid; i++) swap(p[X[i]], p[Y[i]]);
		for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
		for (int i = 0; i < N; i++)
		{
			if (ind[i] != p[cur[i]]) s.push_back(ind[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]]);
			while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
			{
				s.pop_back();
			}
			int f1 = -1, f2 = -1;
			if (!s.empty())
			{
				f1 = idx[s.back()];
				f2 = idx[p[cur[f1]]];
				s.pop_back();
			}
			if (f1 != -1) 
			{
				swap(cur[f1], cur[f2]);
			}
		}
		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;
	}
	s.clear();
	iota(p, p + N, 0);
	iota(u, u + N, 0);
	for (int i = 0; i < l; i++) swap(p[X[i]], p[Y[i]]);
	for (int i = 0; i < N; i++) ind[i] = i, idx[i] = i, cur[i] = S[i];
	for (int i = 0; i < N; i++)
	{
		if (ind[i] != p[cur[i]]) s.push_back(ind[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]]);
		while (!s.empty() && s.back() == p[cur[idx[s.back()]]])
		{
			s.pop_back();
		}
		int f1 = -1, f2 = -1;
		if (!s.empty())
		{
			f1 = idx[s.back()];
			f2 = idx[p[cur[f1]]];
			s.pop_back();
		}
		if (f1 != -1) 
		{
			P[i] = f1, Q[i] = f2;
			swap(cur[f1], cur[f2]);
		}
		else P[i] = Q[i] = 0;
	}
	return l;
}

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