Cod sursa(job #1105202)

Utilizator s1mpMihai Alexandru s1mp Data 11 februarie 2014 16:25:12
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<iostream>
#include<fstream>

#define Nmax 3000001

using namespace std;

int M[Nmax];
int sol;

int QuickSelect(int p, int u, int K) {
	if (p == u) {
		return M[p];
	} else {
		int pivot = M[p + (rand() % (u - p + 1))];
		int i = p;
		int j = u;
		while (i <= j) {
			while (M[i] < pivot) {
				i++;
			}
			while (M[j] > pivot) {
				j--;
			}
			if (i <= j) {
				swap(M[i], M[j]);
				i++;
				j--;
			}
		}
		if (K <= j - p + 1) {
			return QuickSelect(p,j,K);
		} else {
			return QuickSelect(j+1,u,K-j+p-1);
		} 
	}
}

int main() {
	ifstream f("sdo.in");
	ofstream g("sdo.out");
	int N,K;
	f>>N;
	f>>K;
	for(int i = 1; i <= N; i++) {
		f>>M[i];
	}
	g<<QuickSelect(1,N,K);
	f.close();
	g.close();
	return 0;
}