Submission #1243042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243042		KindaGoodGames	정렬하기 (IOI15_sorting)	C++20	0 / 100	2 ms	584 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()-1)/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);

	map<int,int> pos;
	for(int i = 0; i < n; i++){
		arr[i] = S[i];
		pos[arr[i]] = i;
	}


	if(n == 1){
		return 0;
	}
	if(n == 2){
		if(arr[0] == 1 && arr[1] == 0){
			return 1;
		}else{
			return 0;
		}
	}

	if(Y[0] == 0){     
		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();
	}

	swaps.push_back({0, pos[1]});
	swap(arr[0], arr[pos[1]]);
	swap(arr[X[0]], arr[Y[0]]);
 
	for(int i = 0; i < n; i++){ 
		pos[arr[i]] = i;
	}
	swaps.push_back({0, pos[0]});
	if(arr[0] != 0){
		swap(arr[0], arr[pos[0]]);
		swap(arr[X[1]], arr[Y[1]]); 
	}else{ 
		swap(arr[1], arr[pos[0]]);
		swap(arr[X[1]], arr[Y[1]]); 
	}

	quicksort(2,n-1);
	for(int i = 0; i < swaps.size(); i++){
		if(i > 1){ 
			swap(arr[0], arr[1]);
		}
	}

	if(arr[0] == 1 && arr[1] == 0){
		if(X[0] == 0 && Y[0] == 1){
		swaps.push_back({0,0});
		}else{
			swaps.push_back({0,1}); 
		}
		swap(arr[0], arr[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