Submission #640217

#	Time	Username	Problem	Language	Result	Execution time	Memory
640217		ggoh	Sorting (IOI15_sorting)	C++14	100 / 100	406 ms	20188 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int p=-1,q=M,h,st[200002],sz=0;;
	vector<int>C(N),R(N),go(N),rev(N);
	while(p!=q-1)
	{
		h=(p+q)/2;
		for(int i=0;i<N;i++)C[i]=S[i];
		for(int i=0;i<h;i++)swap(C[X[i]],C[Y[i]]);
		sz=0;
		for(int i=0;i<N;i++)
		{
			go[C[i]]=i;
			rev[i]=C[i];
			if(go[C[i]]!=C[i])
			{
				st[sz++]=C[i];
			}
		}
		for(int i=0;i<N;i++)
		{
			C[i]=S[i];
			R[S[i]]=i;
		}
		for(int i=0;i<h;i++)
		{
			swap(R[C[X[i]]],R[C[Y[i]]]);
			swap(C[X[i]],C[Y[i]]);
			while(sz>0 && go[st[sz-1]]==st[sz-1])sz--;
			if(sz>0)
			{
				int ch=st[sz-1];
				int j=rev[ch];
				sz--;
				swap(C[R[j]],C[R[ch]]);
				swap(R[j],R[ch]);
				swap(rev[go[j]],rev[go[ch]]);
				swap(go[j],go[ch]);
			}
		}
		int s=0;
		for(int i=0;i<N;i++)if(go[i]==i)s++;
		if(s==N)q=h;
		else p=h;
	}

	for(int i=0;i<N;i++)C[i]=S[i];
	for(int i=0;i<q;i++)swap(C[X[i]],C[Y[i]]);
	sz=0;
	for(int i=0;i<N;i++)
	{
		go[C[i]]=i;
		rev[i]=C[i];
		if(go[C[i]]!=C[i])st[sz++]=C[i];
	}
	for(int i=0;i<N;i++)
	{
		C[i]=S[i];
		R[S[i]]=i;
	}
	for(int i=0;i<q;i++)
	{
		swap(R[C[X[i]]],R[C[Y[i]]]);
		swap(C[X[i]],C[Y[i]]);
		while(sz>0 && go[st[sz-1]]==st[sz-1])sz--;
		if(sz>0)
		{
			int ch=st[sz-1];
			int j=rev[ch];
			sz--;
			swap(C[R[j]],C[R[ch]]);
			swap(R[j],R[ch]);
			P[i]=R[j],Q[i]=R[ch];
			swap(rev[go[j]],rev[go[ch]]);
			swap(go[j],go[ch]);
		}
		else P[i]=Q[i]=0;
	}
	return 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