Cod sursa(job #1509936)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 24 octombrie 2015 14:07:40
Problema Statistici de ordine Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

#define NMAX 3000005

using namespace std;

ifstream fin("sdo.in");
ofstream fout("sdo.out");

int v[NMAX];


int nthElement(int st, int dr, int poz)
{
	int pivot = v[st + rand() % (dr - st + 1)];
	int i = st;
	int j = dr;

	do
	{
		while (v[i] < pivot && i < dr) ++i;
		while (v[j] > pivot && j > st) --j;

		if (i < j) swap(v[i], v[j]);

	} while (i < j);

	if (j - st + 1 == poz) return v[j];
	if (j - st + 1 < poz) return nthElement(i + 1, dr, poz - i + st - 1);
	return nthElement(st, j - 1, poz);
}

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

	int n, k;

	fin >> n >> k;
	for (int i = 0; i < n; ++i)
		fin >> v[i];

	fout << nthElement(0, n - 1, k) << '\n';
	return 0;
}