Submission #599148

#	Time	Username	Problem	Language	Result	Execution time	Memory
599148		sofapuden	Sorting (IOI15_sorting)	C++14	100 / 100	581 ms	28860 KiB

sorting

#include "sorting.h"
#include<bits/stdc++.h>

using namespace std;

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int l = 0, r = M, bes = M;
	while(l <= r){
		vector<int> seq(N);
		for(int i = 0; i < N; ++i)seq[i] = S[i];
		int m = (l+r)>>1;
		for(int i = 0; i < m; ++i)swap(seq[X[i]],seq[Y[i]]);
		int cn = 0;
		for(int i = 0; i < N; ++i){
			while(seq[i] != i){
				cn++;
				swap(seq[i],seq[seq[i]]);
			}
		}
		if(cn > m)l = m+1;
		else bes = m, r = m-1;
	}
	map<int,int> Ma;
	for(int i = 0; i < N; ++i)Ma[S[i]] = i;
	vector<int> seq(N);
	for(int i = 0; i < N; ++i)seq[i] = S[i];
	for(int i = 0; i < bes; ++i)swap(seq[X[i]],seq[Y[i]]);
	int cn = 0;
	for(int i = 0; i < N; ++i){
		while(seq[i] != i){
			P[cn] = seq[i];
			Q[cn] = seq[seq[i]];
			cn++;
			swap(seq[i],seq[seq[i]]);
		}
	}
	for(int i = 0; i < bes; ++i){
		swap(S[X[i]],S[Y[i]]);
		swap(Ma[S[X[i]]],Ma[S[Y[i]]]);
		P[i] = Ma[P[i]];
		Q[i] = Ma[Q[i]];
		swap(S[P[i]],S[Q[i]]);
		swap(Ma[S[P[i]]],Ma[S[Q[i]]]);
	}
	return bes;
}

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