Cod sursa(job #612986)

Utilizator Teodor94Teodor Plop Teodor94 Data 14 septembrie 2011 09:56:36
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>

const int N=100;

int v[N],n,k;

void schimba(int &x,int &y)
{
	int aux=x;
	x=y;
	y=aux;
}

int partitie(int st,int dr)
{
	int poz,i;
	poz=st+rand()%(dr-st+1);
	schimba(v[dr],v[poz]);
	for (i=poz=st;i<dr;++i)
		if (v[i]<v[dr])
			schimba(v[i],v[poz++]);
	schimba(v[dr],v[poz]);
	return poz;
}

void citire()
{
	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]);
}

int bin(int st,int dr,int k)
{
	int r;
	while ((r=partitie(st,dr)) != k)
		if (r<k)
			st=r+1;
		else
			dr=r-1;
	return v[k];
}

int main()
{
	citire();
	printf("%d\n",bin(1,n,k));
	return 0;
}