Submission #1226277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226277		abdelhakim	Sorting (IOI15_sorting)	C++20	100 / 100	291 ms	27832 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ' ' <<x << endl;
#define ll long long
using namespace std;
vector<ll> ind;
vector<ll> dest;
vector<ll> recip;
vector<ll> s;
bool is_sorted()
{
	for (int i=0;i<s.size();i++)
	{
		if(s[i]!=i) return false;
	}
	return true;
}
void swp(ll i, ll j)
{
	swap(s[i],s[j]);
	swap(ind[s[i]],ind[s[j]]);
	swap(dest[s[i]],dest[s[j]]);
	recip[dest[s[i]]]=s[i];
	recip[dest[s[j]]]=s[j];
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
	Q[0] = 0;
	ind.resize(N);
	dest.resize(N);
	recip.resize(N);
	for (int i=0;i<N;i++)
	{
		s.push_back(S[i]);
	}
	if(is_sorted())
	{
		for (int i=0;i<M;i++)
		{
			P[i]=0;
			Q[i]=0;
		}
		return 0;
	}
	ll l=1;
	ll r=M;
	ll mine=M;
	while(l<=r)
	{
		ll mid=(l+r)>>1;
		for (int i=0;i<N;i++)
		{
			s[i]=S[i];
			ind[s[i]]=i;
		}
		vector<ll> p(M);
		vector<ll> q(M);
		for (int i=0;i<M;i++) 
		{
			p[i]=0;
			q[i]=0;
		}
		vector<ll> l3iba(N);
		for (int i=0;i<N;i++) l3iba[i]=s[i];
		for (int i=0;i<mid;i++)
		{
			swap(l3iba[X[i]],l3iba[Y[i]]);
		}
		for (int i=0;i<N;i++)
		{
			dest[l3iba[i]]=i;
			recip[dest[l3iba[i]]]=l3iba[i];
		}
		ll cur=0;
		for (int i=0;i<mid;i++)
		{
			swap(s[X[i]],s[Y[i]]);
			swap(ind[s[X[i]]],ind[s[Y[i]]]);
			for (;cur<N;cur++)
			{
				if(dest[cur]!=cur)
				{
					p[i]=ind[cur];
					q[i]=ind[recip[cur]];
					swp(p[i],q[i]);
					cur++; 
					break;
				}
			}
		}
		if(is_sorted())
		{
			mine=mid;
			for (int i=0;i<M;i++)
			{
				P[i]=p[i];
				Q[i]=q[i];
			}
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	return mine;
}

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