Submission #1225517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225517		Hamed_Ghaffari	Sorting (IOI15_sorting)	C++20	100 / 100	141 ms	13952 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 2e5+5;

int b[MXN], whb[MXN], p[MXN], a[MXN], wh[MXN];

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	if(N==1) return 0;
	auto check = [&](int lim) -> bool {
		iota(whb, whb+N, 0);
		for(int i=0; i<lim; i++)
			swap(whb[X[i]], whb[Y[i]]);
		for(int i=0; i<N; i++)
			p[whb[i]] = i;
		iota(whb, whb+N, 0);
		iota(b, b+N, 0);
		for(int i=0; i<N; i++)
			wh[a[i] = S[i]] = i;
		int ptr=0;
		for(int i=0, j; i<N; i++)
			if(a[i]!=p[i]) {
				swap(b[whb[X[ptr]]], b[whb[Y[ptr]]]);
				swap(whb[X[ptr]], whb[Y[ptr]]);
				
				j = wh[p[i]];
				P[ptr] = b[i];
				Q[ptr] = b[j];
				ptr++;
				swap(a[i], a[j]);
				swap(wh[a[i]], wh[a[j]]);
			}
		if(ptr>lim) return 0;
		for(int i=ptr; i<lim; i++) P[i] = Q[i] = 0;
		return ptr<=lim;
	};

	int l=-1, r=N-1, mid;
	while(r-l>1) {
		mid = ((l+r)>>1);
		(check(mid) ? r : l) = mid;
	}
	check(r);
	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