Cod sursa(job #542300)

Utilizator ChallengeMurtaza Alexandru Challenge Data 26 februarie 2011 10:26:58
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

const char InFile[]="sdo.in";
const char OutFile[]="sdo.out";
const int MaxN=3000111;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,K,V[MaxN];

inline int randomInt(int minv, int maxv)
{
	return minv+(rand()%(maxv-minv+1));
}

inline int partition(int st, int dr)
{
	int pivot=V[randomInt(st,dr)];
	--st;
	++dr;
	while(true)
	{
		do
		{
			++st;
		}while(V[st]<pivot);
		do
		{
			--dr;
		}while(pivot<V[dr]);
		if(st<dr)
		{
			swap(V[st],V[dr]);
		}
		else
		{
			return dr;
		}
	}
	return 0;
}

int sdo(int st, int dr, int pos)
{
	if(st==dr)
	{
		return V[st];
	}
	int m=partition(st,dr);
	int left=m-st+1;
	if(pos<=left)
	{
		return sdo(st,m,pos);
	}
	return sdo(m+1,dr,pos-left);
}

int main()
{
	srand((unsigned int)(time(NULL)));

	fin>>N>>K;
	for(register int i=1;i<=N;++i)
	{
		fin>>V[i];
	}
	fin.close();

	fout<<sdo(1,N,K);
	fout.close();
	return 0;
}