Submission #210938

#	Time	Username	Problem	Language	Result	Execution time	Memory
210938		autumn_eel	Sorting (IOI15_sorting)	C++14	74 / 100	49 ms	10720 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;

int s[3000],spos[3000];
int p[3000],ppos[3000];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	if(is_sorted(S,S+N))return 0;
	auto C=[&](int R){
		rep(i,N)p[i]=i,s[i]=S[i];
		for(int i=R-1;i>=0;i--){
			swap(p[X[i]],p[Y[i]]);
		}
		rep(i,N){
			ppos[p[i]]=i;
			spos[s[i]]=i;
		}
		int g=0;
		rep(i,R){
			swap(p[X[i]],p[Y[i]]);
			swap(ppos[p[X[i]]],ppos[p[Y[i]]]);
			swap(s[X[i]],s[Y[i]]);
			swap(spos[s[X[i]]],spos[s[Y[i]]]);
			while(g<N&&spos[g]==ppos[g])g++;
			if(g==N){
				P[i]=Q[i]=0;continue;
			}
			int a=spos[g],b=ppos[g];
			P[i]=a;Q[i]=b;
			swap(s[a],s[b]);
			swap(spos[s[a]],spos[s[b]]);
		}
		rep(i,N)assert(p[i]==i);
		rep(i,N){
			if(s[i]!=i)return false;
		}
		return true;
	};
	int ok=N,ng=0;
	while(ok-ng>1){
		int R=(ok+ng)/2;
		if(C(R))ok=R;
		else ng=R;
	}
	C(ok);
	return ok;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:9:39: warning: unused parameter 'M' [-Wunused-parameter]
 int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
                                       ^

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