Cod sursa(job #855952)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 15 ianuarie 2013 20:44:34
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;

int n, k, v[3000001], win;

void quickSort(int stg, int dpt)
{
	if (stg < dpt)
	{
		srand(time(NULL));
		int i=stg, j=dpt, rng=rand()%(dpt-stg+1) + stg;
		int m = v[rng];
		while (i <= j)
		{
			while (v[i] < m)
				++i;
			while (v[j] > m)
				--j;
			if (i <= j)
			{
				v[i] ^= v[j];
				v[j] ^= v[i];
				v[i] ^= v[j];
				++i; --j;
			}
		}
		
		if (i-j == 2 && k == i-1)
			win = v[i-1];
		else
			if (k >= i)
				quickSort(i, dpt);
			else quickSort(stg, j);
	}
	else win = v[stg];
}

int main()
{
	freopen("sdo.in", "r", stdin);
	freopen("sdo.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i=1; i<=n; ++i)
		scanf("%d", &v[i]);
	
	quickSort(1, n);
	printf("%d", win);
	return 0;
}