Cod sursa(job #682584)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 19 februarie 2012 10:53:45
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int e[3000002],n,h;
int part(int st,int dr){
	int i,j,pivot;
	i=st-1;
	j=dr+1;
	pivot=e[st+rand()%(dr-st+1)];
	while(3){
		do{
			++i;
		}while(e[i]<pivot);
		
		do{
			--j;
		}while(e[j]>pivot);
		if(i<j)
			swap(e[i],e[j]);
		else{
			return j;
			
		}
	}
	return 0;
}
void quick(int st,int dr,int k){
	if(st==dr)
		return ;
	int x=part(st,dr);
	int d=x-st+1;
	if(d>=k)
		quick(st,x,k);
	else
		quick(x+1,dr,k-d);
}
int main (){
	f>>n>>h;
	for(int i=1;i<=n;i++)
		f>>e[i];
	quick(1,n,h);
	g<<e[h]<<"\n";
	return 0;
}