Cod sursa(job #804163)

Utilizator igsifvevc avb igsi Data 28 octombrie 2012 23:05:23
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
/*
 * Using basic (non-random) quicksort partition algorithm
 */
#include <fstream>

using namespace std;

int n, k, v[3000005];

int select (int l, int r)
{
	int i, j, t;

	for (i = l - 1, j = l; j < r; ++j)
		if (v[r] >= v[j])
		{
			++i;
			t = v[i];
			v[i] = v[j];
			v[j] = t;
		}
  	t = v[++i];
	v[i] = v[r];
	v[r] = t;

	if (i == k) return v[i];
	else if (i < k) return select (i+1, r);
	else return select (l, i-1);
}

int main()
{
	int i;
	ifstream fin ("sdo.in");
	ofstream fout ("sdo.out");

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

	fout << select (1, n) << endl;

	fin.close();
	fout.close();
	return 0;
}