Cod sursa(job #429069)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 martie 2010 20:03:49
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define Nmax 3000010

int v[Nmax],K,i,n;

void swap(int &a, int &b)
{
	int aux=a; a=b; b=aux;
}


int pozitie(int i, int j)
{
	int p= v [ i + rand()%(j-i+1) ] ;
	
	while(1)
	{
		while( v[i]<p ) i++;
		while( v[j]>p ) j--;
		
		if(i<j) swap(v[i],v[j]);
		else break;
	}
	
	return j;
}

void quick(int s, int d, int k)
{
	int p=pozitie(s,d);
	int t=p-s+1;
	
	if( t > k ) quick(s,p-1,k);
	else
		if( t < k ) quick(p+1,d,t-k);
}

int main()
{
	srand(time(0));
	
	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]);
	
	quick(1,n,K);
	
	printf("%d",v[K]);
	
	return 0;
}