Cod sursa(job #429077)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 29 martie 2010 20:07:21
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<fstream>
#include<time.h>
#include<stdlib.h>
#define Nmax 3000010
using namespace std;
int v[Nmax],K,i,n;

void swap(int &a, int &b)
{
	int aux=a; a=b; b=aux;
}


int pozitie(int i, int j)
{
	int p= v [ i + rand()%(j-i+1) ] ;
	
	while(1)
	{
		while( v[i]<p ) i++;
		while( v[j]>p ) j--;
		
		if(i<j) swap(v[i],v[j]);
		else break;
	}
	
	return j;
}

void quick(int s, int d, int k)
{
	if(s==d) return ;
	
	int p=pozitie(s,d);
	int t=p-s+1;
	
	if( t > k ) quick(s,p-1,k);
	else
		if( t < k ) quick(p+1,d,t-k);
}

int main()
{
	srand(time(0));
	
	ifstream f("sdo.in");
	ofstream g("sdo.out");
	
	f>>n>>K;
	
	for(i=1;i<=n;i++)
		f>>v[i];
	
	quick(1,n,K);
	
	g<<v[K];
	
	f.close();
	g.close();	
	return 0;
}