Submission #135300

#	Time	Username	Problem	Language	Result	Execution time	Memory
135300		20160161simone	Sorting (IOI15_sorting)	C++14	100 / 100	312 ms	21944 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define NN 200010
using namespace std;
int a[NN],b[NN],c[NN][2],*x,*y,*s,k,n,m;
bool check(int m0)
{
	for(int i=0;i<n;i++) a[i]=s[i];
	for(int i=0;i<m0;i++) swap(a[x[i]],a[y[i]]);
	for(int i=0;i<n;i++) b[a[i]]=i;
	k=0;
	for(int i=0;i<n;i++)
	{
		if(b[i]!=i)
		{
			c[k][0]=i,c[k][1]=a[i];
			swap(a[b[i]],a[b[c[k][1]]]);
			swap(b[i],b[c[k][1]]);
			k++;
		}
	}
	if(k<=m0) return 1;
	return 0;
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N,m=M,x=X,y=Y,s=S;
    int l=0,r=m,ans_num=m;
    while(l<=r)
	{
    	int mid=(l+r)/2;
    	if(check(mid)==1) ans_num=mid,r=mid-1;
    	else l=mid+1;
	}
	check(ans_num);
	for(int i=0;i<n;i++) a[i]=s[i];
	for(int i=0;i<n;i++) b[a[i]]=i;
	for(int i=0;i<ans_num;i++)
	{
		swap(a[x[i]],a[y[i]]);
		swap(b[a[x[i]]],b[a[y[i]]]);
		if(i<k)
		{
			swap(a[P[i]=b[c[i][0]]],a[Q[i]=b[c[i][1]]]);
			swap(b[c[i][0]],b[c[i][1]]);
		}
		else Q[i]=0,P[i]=0;
	}
	return ans_num;
}

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