Cod sursa(job #557418)

Utilizator BitOneSAlexandru BitOne Data 16 martie 2011 17:34:39
Problema Statistici de ordine Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <ctime>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 3000011

using namespace std;
int v[N_MAX];
inline int MedianOf3( int x, int y, int z )
{
	int w[]={ x, y, z }, i, j;
	for( i=0; i <= 1; ++i )
		for( j=i+1; j <= 2; ++j )
			if( w[i] > w[j] )
				swap( w[i], w[j] );
	return w[1];
}
inline void FindKth( int left, int right, int k )
{
	if( left < right )
	{
		//int xRandom=rand()%(right-left+1)+left;
		//swap( v[(left+right)/2], v[xRandom] );
		int pValue=MedianOf3( v[left], v[(left+right)/2], v[right] ), lleft, rright, q;
		for( lleft=left-1, rright=right+1; ; )
		{
			for( ++lleft; lleft <= right && pValue > v[lleft]; ++lleft );
			for( --rright; rright >= left && pValue < v[rright]; --rright );
			if( lleft >= rright )
				break;
			swap( v[lleft], v[rright] );
		}
		q=rright-left+1;
		if( q >= k )
			FindKth( left, q, k );
		else FindKth( q+1, right, k-q );
	}
}
int main()
{
	srand( time( NULL ) );
	int N, K;
	ifstream in( "sdo.in" );
	in>>N>>K;
	copy( istream_iterator<int>(in), istream_iterator<int>(), v+1 );
	FindKth( 1, N, K );
	ofstream out( "sdo.out" );
	out<<v[K]<<'\n';
}