Cod sursa(job #659113)

Utilizator danieladDianu Daniela danielad Data 10 ianuarie 2012 01:20:41
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;
int v[3000002],n,k;
ifstream f("sdo.in");
ofstream g("sdo.out");
int part(int left,int right){
	int i=left,j=right,pivot=v[left+rand()%(right-left+1)];
	while(1){
		while(v[i]<pivot)i++;
		while(v[j]>pivot)j--;
		if(i<j)
			swap(v[i],v[j]);
		else
			return j;
	}
}
void quick(int left,int right,int k){
	if(left==right)return;
	int m=part(left,right);
	int x=m-left;
	if(x>=k)
		quick(left,m,k);
	else 
		quick(m+1,right,k-x);
}
int main(){
	f>>n>>k;
	for(int i=1;i<=n;i++)
		f>>v[i];
	quick(1,n,k);
	g<<v[k]<<"\n";
	return 0;
}