Cod sursa(job #450046)

Utilizator S7012MYPetru Trimbitas S7012MY Data 7 mai 2010 17:02:35
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;


int n,v[500001];

int partitie(int p, int r) {
	int x,i,j;
	x=v[p];
	i=p-1;
	j=r+1;
	while (1) {
		do {
			j--;
		} while (v[j]>x);
		do {
			i++;
		}
		while(v[i]<x);
		if(i<j) swap(v[i],v[j]);
		else return j;
	}
}

int partitie_aleatoare (int p, int r) {
	int i;
	i=(rand() % (r-p)) + p + 1;
	//i=(r+p)/2;
	swap(v[p],v[i]);
	return partitie(p,r);
}

int s_aleator(int p, int r,int i) {
	int q,k;
	if(p==r) return v[p];
	q=partitie_aleatoare(p,r);
	k=q-p+1;
	if(i<=k) return s_aleator(p,q,i);
	else return s_aleator(q+1,r,i-k);
}

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