Submission #1243035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243035		KindaGoodGames	Sorting (IOI15_sorting)	C++20	20 / 100	2 ms	580 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);
			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);
    evil.resize(M);
	for(int i = 0; i < n; i++){
		arr[i] = S[i];
	}
    for(int i = 0; i < M; i++){
        evil[i] = {X[i], Y[i]};
    }

	quicksort(0,n-1);

    // for(int i = 0; i < n; i++){
    //     for(int j = i+1; j < n; j++) {
    //         if(arr[i] > arr[j]) {
    //             doSwap(i,j);
    //         }
    //     }
    // }

    if(arr[0] != 0){
        doSwap(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: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 20
• Subtask 6: 0 / 26