Submission #292347

#	Time	Username	Problem	Language	Result	Execution time	Memory
292347		VodkaInTheJar	Sorting (IOI15_sorting)	C++14	100 / 100	191 ms	20444 KiB

sorting

#include <bits/stdc++.h>
 
using namespace std;

const int maxn = 2e5 + 3; 

int n; 
int t[maxn];
int pos[maxn];
bool used[maxn];

int get_cycles()
{
	for (int i = 0; i < n; i++)
	used[i] = false; 
	
	int ans = 0; 
	for (int i = 0; i < n; i++)
	if (!used[i])
	{
		ans++;
		int j = i;
		while (!used[j])
		{
			used[j] = true;
			j = t[j];
		}
	}
	
	return ans; 
}

int findSwapPairs(int _n, int s[], int m, int x[], int y[], int p[], int q[])
{
	n = _n; 
	for (int i = 0; i < n; i++)
	pos[s[i]] = i;
	
	for (int i = 0; i < n; i++)
	t[i] = s[i];
	
	if (get_cycles() == n)
	return 0; 
	
	int low = 0, high = m-1;
	while (low < high)
	{
		int mid = (low + high) / 2; 
		for (int i = 0; i < n; i++)
		t[i] = s[i];
		
		for (int i = 0; i <= mid; i++)
		swap(t[x[i]], t[y[i]]);
		
		if (n - get_cycles() <= mid + 1)
		high = mid;
		
		else 
		low = mid + 1; 
	}
	
	for (int i = 0; i < n; i++)
		t[i] = s[i];
	
	for (int i = 0; i < m; i++)
	{
		swap(t[x[i]], t[y[i]]);
		
		if (i == low)
		{
			vector <pair <int, int> > v; 
			for (int j = 0; j < n; j++)
			used[j] = false; 
			
			for (int j = 0; j < n; j++)
			if (!used[j])
			{
				int curr = j;
				int last = j; 
				while (!used[curr])
				{
					used[curr] = true;
					if (curr != last)
					v.push_back({last, curr});
					
					last = curr;
					curr = t[curr];
				}
			}
			
			for (int j = 0; j <= i; j++)
			{
				if (x[j] != y[j])
				{
					swap(pos[s[x[j]]], pos[s[y[j]]]);
					swap(s[x[j]], s[y[j]]);
				}
				
				if (j < (int)v.size())
				{
					p[j] = pos[v[j].first];
					q[j] = pos[v[j].second];
					swap(pos[s[p[j]]], pos[s[q[j]]]);
					swap(s[p[j]], s[q[j]]);
				}
				
				else 
				p[j] = q[j] = 0; 
			}
			
			return i + 1; 
		}
	}
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^

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