Cod sursa(job #1166593)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 aprilie 2014 18:10:09
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 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 Random(const int &st, const int &dr)
{
	return st+(rand()%(dr-st+1));
}

inline int part(int st, int dr)
{
	int i = st - 1, j = dr + 1, val = V[Random(st,dr)];

	while (1)
	{
		do
		{
			++i;
		} while (V[i] < val);

		do
		{
			--j;
		} while (val < V[j]);
		if (i < j)
		{
			swap(V[i], V[j]);
		}
		else
		{
			return j;
		}
	}
}

int sdo(int st, int dr, int k)
{
	if (st == dr)
	{
		return V[st];
	}
	int p = part(st,dr);

	if (k<=p-st+1)
	{
		return sdo(st, p, k);
	}
	else
	{
		return sdo(p + 1, dr, k - (p-st+1));
	}
}

int main()
{
	//srand(time(NULL));
	srand(30);

	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;
}