Submission #1243113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243113		KindaGoodGames	Sorting (IOI15_sorting)	C++20	20 / 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<pii> evil;
vector<int> arr;

int getMedian(vector<int> arr){
	sort(arr.begin(),arr.end());
	return arr[(arr.size()-1)/2];
}
void doSwap(int a, int b){  
    swaps.push_back({a,b}); 
    swap(arr[a], arr[b]);
    swap(arr[evil[swaps.size()-1].first], arr[evil[swaps.size()-1].second]); 
}
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){
			doSwap(i,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;
	}

    evil.resize(M);
    for(int i = 0; i < M; i++){
        evil[i] = {X[i], Y[i]};
    }

	// ST 1 & 2
	if(Y[0] == 0){     
		
		if(n == 1){
			return 0;
		}
		if(n == 2){
			if(arr[0] == 1 && arr[1] == 0){
				P[0] = 0;
				Q[0] = 1;
				return 1;
			}else{
				return 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();
	}

	if(n == 1){ 
		return 0;
	}
	if(n == 2){ 
		if(arr[0] == 1 && arr[1] == 0){
			return 1;
		}else{
			return 0;
		}
	}
	doSwap(0, pos[1]); 
 
	for(int i = 0; i < n; i++){ 
		pos[arr[i]] = i;
	} 
	if(arr[0] != 0){
		doSwap(0, pos[0]); 
	}else{ 
		doSwap(1, pos[0]); 
	}

	quicksort(2,n-1); 

	if(arr[0] == 1 && arr[1] == 0){
		if(X[0] == 0 && Y[0] == 1){
			doSwap(0,0);
		}else{
			doSwap(0,1);
		} 
	} 

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

	return swaps.size();
}

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