Submission #1223535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223535		boclobanchat	Sorting (IOI15_sorting)	C++20	100 / 100	92 ms	10096 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,ans=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		vector<int> p(n),q(n);
		for(int i=0;i<n;i++) p[i]=i;
		for(int i=mid-1;i+1;i--) swap(p[X[i]],p[Y[i]]);
		for(int i=0;i<n;i++) q[p[i]]=i;
		for(int i=0;i<n;i++) p[i]=q[S[i]];
		for(int i=0;i<n;i++) q[p[i]]=i;
		int cnt=0;
		for(int i=0;i<n;i++)
		{
			int x=i,y=q[i];
			if(x!=y) cnt++,swap(p[x],p[y]),swap(q[p[x]],q[p[y]]);
		}
		if(cnt<=mid) r=mid-1,ans=mid;
		else l=mid+1;
	}
	vector<int> p(n),q(n);
	for(int i=0;i<n;i++) p[i]=i;
	for(int i=ans-1;i+1;i--) swap(p[X[i]],p[Y[i]]);
	for(int i=0;i<n;i++) q[p[i]]=i;
	for(int i=0;i<n;i++) p[i]=q[S[i]];
	for(int i=0;i<n;i++) q[p[i]]=i;
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		int x=i,y=q[i];
		if(x!=y) P[cnt]=x,Q[cnt]=y,cnt++,swap(p[x],p[y]),swap(q[p[x]],q[p[y]]);
	}
	while(cnt<ans) P[cnt]=Q[cnt]=0,cnt++;
	for(int i=0;i<n;i++) p[i]=q[i]=i;
	for(int i=0;i<ans;i++)
	{
		int l=q[X[i]],r=q[Y[i]];
		swap(p[l],p[r]);
		swap(q[p[l]],q[p[r]]);
		P[i]=p[P[i]],Q[i]=p[Q[i]];
	}
	return ans;
}

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