Cod sursa(job #1527208)

Utilizator msschFMI - Enache Alexandru Madalin mssch Data 17 noiembrie 2015 22:04:24
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
using namespace std;
int n,k,v[n3000007];

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

int Quick(int left, int right)
{
	int p = v[(left + right) / 2];

	while (1)
	{
		while (v[left] < p) left++;
		while (v[right] > p) right--;

		if (left < right)
		{
			v[left] = v[left] ^ v[right] ^ (v[right] = v[left]);
			left++;
			right--;
		}
		else
		{
			return right;
		}
	}

	return 0;
}

void Cauta(int left, int right, int k)
{
	int m, nr;

	if(left == right)
	{
		return;
	}

	nr = Quick(left, right);
	m = nr - left + 1;

	if(m >= k)
	{
		Cauta(left, nr, k);
	}
	else
	{
		Cauta(nr+1, right, k-m);
	}
}

int main()
{
	fin >> n >> k;

	for(int i = 1; i <= n; i++)
	{
		fin >> v[i];
	}

	Cauta(1, n, k);

	fout << v[k];

	return 0;
}