Cod sursa(job #1019196)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 30 octombrie 2013 19:38:34
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<cstdlib>
#define dim 500007

using namespace std;


ifstream f("sdo.in");
ofstream g("sdo.out");
int a[dim],n,i,k;

int pivotare(int st,int dr){
	
	int i,j,piv;
	i=st-1;
	j=dr+1;
	piv=a[st+rand()%(dr-st+1)];
	
	
	while(3543231){
		
		do{
			++i;
		}while(a[i]<piv);
		do{
			--j;
		}while(a[j]>piv);
		if(i<j)
			swap(a[i],a[j]);
		else
			return j;
	}
	
	return 0;
}
void quick(int st,int dr,int k){
	
	if(st<dr){
		
		int pivot=pivotare(st,dr);
		int dist=pivot-st+1;
		if(dist>=k)
			quick(st,pivot,k);
		else
			quick(pivot+1,dr,k-dist);
	}
}
int main () {
	
	f>>n>>k;
	
	for(i=1;i<=n;++i)
		f>>a[i];
	
	quick(1,n,k);
	
	g<<a[k]<<"\n";
	
	return 0;
}