제출 #1243003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243003		KindaGoodGames	정렬하기 (IOI15_sorting)	C++20	0 / 100	2 ms	576 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;
	}

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

	quicksort(2,n-1);

	if(X[0] == 0 && Y[0] == 0){
		// do nothing
	}else{
		if(swaps.size() % 2 == 0){
			swaps.push_back({0,0});
		}
	}

	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