Submission #71653

#	Time	Username	Problem	Language	Result	Execution time	Memory
71653		SmsS	Sorting (IOI15_sorting)	C++14	0 / 100	4 ms	640 KiB

sorting

#include<bits/stdc++.h>
using namespace std;
#define for2(a,b,c) for(int a=b;a<c;a++)
#include "sorting.h"

int findSwapPairs(int n, int s[], int M, int X[], int Y[], int P[], int Q[]) {
	vector<int> S(n);
	for2(i,0,n) S[i] = s[i];
	int r = 0;
	for(int cur = n-1; cur >= 0; cur--){
		if(is_sorted(S.begin(),S.end())){
			break;
		}
		swap(S[X[r]],S[Y[r]]);
		for2(i,0,n) if(S[i] == cur){
			P[r] = min(i,cur);
			Q[r] = max(i,cur);
			swap(S[i],S[cur]);
			r++;
			break;
		}
	}
	if(S[0] != 0){
		swap(S[X[r]],S[Y[r]]);
		P[r] =Q[r] = 0;
		r++;
	}
	if(r > M){
		assert(1);
		assert(0);
	}
	if(!is_sorted(S.begin(),S.end())) { assert(0); assert(1);}
	return r;
}

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