Cod sursa(job #1019423)

Utilizator RampageSergiu Caraian Rampage Data 31 octombrie 2013 01:50:49
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <cstdlib>
using namespace std;

ifstream f("sdo.in");
ofstream g("sdo.out");

int v[3000000],n,k;

int partition(int ls, int rd)
{
	int p = v[rand() % rd];
	while (ls<rd)
	{
		while(v[ls]<p)
			ls++;
		while(v[rd]>p)
			rd--;
		if(ls<rd)
		{
			int aux = v[ls];
			v[ls]=v[rd];
			v[rd]=aux;
			ls++;
			rd--;
		}
	}
	return rd;
}

void qs(int ls, int rd)
{
	if (ls<rd)
	{
		int p = partition(ls,rd); 
		if (k-1<p)
			qs(ls,p-1);
		else if (k-1>p)
			qs(p+1,rd);
	}
}   

int main()
{
	f>>n>>k;
	for (int i=0; i<n; ++i)
		f>>v[i];

	qs(0,n-1);
	g<<v[k-1]<<" ";
	return 0;
}