Submission #133649

#	Time	Username	Problem	Language	Result	Execution time	Memory
133649		Mahdi_Jfri	Sorting (IOI15_sorting)	C++14	100 / 100	532 ms	32600 KiB

sorting

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;
const int maxm = 3 * maxn;

int pos[maxn] , src[maxn] , a[maxn];
int p[maxm] , q[maxm] , x[maxm] , pp[maxn] , y[maxm] , n;

vector<int> shit;

bool check(int m)
{
	memcpy(a , src , sizeof src);
	if(!m)
	{
		bool f = 1;
		for(int i = 0; i < n; i++)
			f &= a[i] == i;
		return f;
	}

	swap(a[x[0]] , a[y[0]]);
	for(int i = 0; i < n; i++)
		pos[i] = i , shit.pb(i);

	for(int i = m - 1; i > 0; i--)
		swap(pos[x[i]] , pos[y[i]]);

	for(int i = 0; i < n; i++)
		pp[a[i]] = i;

	int pt = 0;
	for(int i = 0; i < m; i++)
	{
		p[i] = 0 , q[i] = 0;
		while(!shit.empty())
		{
			int j = shit.back();
			shit.pop_back();
			if(pos[j] != a[j])
			{
				int ind = pp[pos[j]];
				swap(a[ind] , a[j]);
				p[i] = ind , q[i] = j;
				swap(pp[a[ind]] , pp[a[j]]);
				break;
			}
		}

		if(i + 1 < m)
		{
			shit.pb(x[i + 1]);
			shit.pb(y[i + 1]);
			swap(pp[a[x[i + 1]]] , pp[a[y[i + 1]]]);
			swap(a[x[i + 1]] , a[y[i + 1]]);
			swap(pos[x[i + 1]] , pos[y[i + 1]]);
		}
	}

	bool f = 1;
	for(int i = 0; i < n; i++)
		f &= a[i] == i;
	return f;
}

int findSwapPairs(int N, int A[], int m, int X[], int Y[], int P[], int Q[])
{
	n = N;
	for(int i = 0; i < n; i++)
		src[i] = A[i];

	for(int i = 0; i < m; i++)
		x[i] = X[i] , y[i] = Y[i];

	int l = 0 , r = m;
	if(check(l))
		return l;

	while(r - l > 1)
	{
		int m = (l + r) / 2;
		if(check(m))
			r = m;
		else
			l = m;
	}

	check(r);
	for(int i = 0; i < r; i++)
		P[i] = p[i] , Q[i] = q[i];
	return r;
}

Compilation message (stderr)

sorting.cpp: In function 'bool check(int)':
sorting.cpp:38:6: warning: unused variable 'pt' [-Wunused-variable]
  int pt = 0;
      ^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:87:7: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   int m = (l + r) / 2;
       ^
sorting.cpp:72:39: note: shadowed declaration is here
 int findSwapPairs(int N, int A[], int m, int X[], int Y[], int P[], int Q[])
                                       ^

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