Submission #1242990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242990		KindaGoodGames	Sorting (IOI15_sorting)	C++20	0 / 100	1 ms	580 KiB

sorting

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

using namespace std;

#define pii pair<int,int>
vector<pii> swaps;
vector<int> arr;

int getMedian(vector<int> arr){
	sort(arr.begin(),arr.end());
	return arr[(arr.size())/2];
}

void quicksort(int l, int r){
	if(l == r) return;

	vector<int> cur;
	for(int i = l; i <= r; i++){
		cur.push_back(arr[i]);
	}

	int mid = l+((cur.size()-1)/2);

	int med = getMedian(cur);
	int rpt = r;
	for(int i = l; i <= mid; i++){
		while(rpt > cur.size()/2 && arr[rpt] > med){
			rpt--;
		}

		if(arr[i] > med){
			swaps.push_back({i,rpt}); 
			swap(arr[i], arr[rpt]);
			rpt--;
		}
	}

	quicksort(l, mid);
	quicksort(mid+1, r);
}

int findSwapPairs(int n, int S[], int M, int X[], int Y[], int P[], int Q[]) {
	int ops = 0;
	arr.resize(n);
	for(int i = 0; i < n; i++){
		arr[i] = S[i];
	}

	quicksort(0,n-1);

	for(int i = 0; i < swaps.size(); i++){
		P[i] = swaps[i].first;
		Q[i] = swaps[i].second;
	}

	return swaps.size();
}

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