Submission #131716

#	Time	Username	Problem	Language	Result	Execution time	Memory
131716		nxteru	Sorting (IOI15_sorting)	C++14	100 / 100	230 ms	25580 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
int n,m,s[200005],x[600005],y[600005],t[200005],a[200005];
bool vis[200005];
bool check(int p){
	for(int i=0;i<n;i++)t[i]=s[i];
	for(int i=0;i<p;i++)swap(t[x[i]],t[y[i]]);
	int cnt=n;
	for(int i=0;i<n;i++)vis[i]=false;
	for(int i=0;i<n;i++){
		int v=i;
		if(!vis[i])cnt--;
		while(!vis[v]){
			vis[v]=true;
			v=t[v];
		}
	}
	return cnt<=p;
}
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int p[],int q[]){
	n=N,m=M;
	for(int i=0;i<n;i++)s[i]=S[i];
	for(int i=0;i<m;i++)x[i]=X[i],y[i]=Y[i];
	int l=-1,r=n;
	while(r-l>1){
		int o=(l+r)/2;
		if(check(o))r=o;
		else l=o;
	}
	for(int i=0;i<n;i++)t[i]=s[i];
	for(int i=0;i<r;i++)swap(t[x[i]],t[y[i]]);
	for(int i=0;i<n;i++)vis[i]=false;
	int c=0;
	for(int i=0;i<n;i++){
		int v=i;
		while(!vis[v]){
			vis[v]=true;
			if(vis[t[v]])break;
			p[c]=v;
			q[c]=t[v];
			c++;
			v=t[v];
		}
	}
	for(int i=0;i<n;i++)t[i]=s[i],a[s[i]]=i;
	for(int i=0;i<c;i++){
		swap(t[x[i]],t[y[i]]);
		a[t[x[i]]]=x[i];
		a[t[y[i]]]=y[i];
		p[i]=a[p[i]];
		q[i]=a[q[i]];
		swap(t[p[i]],t[q[i]]);
		a[t[p[i]]]=p[i];
		a[t[q[i]]]=q[i];
	}
	for(int i=c;i<r;i++)p[i]=0,q[i]=0;
	return r;
}

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