Cod sursa(job #2059431)

Utilizator theodor.vladTheodor Vlad theodor.vlad Data 6 noiembrie 2017 23:40:14
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstdlib>

using namespace std;
ifstream fin("statisticiordine.in");
ofstream fout("statisticiordine.out");

void citire();
void afisare();
void kth_element(int, int, int);
int partition(int, int);

int n, k;
long long int a[300005];

int main()
{
	citire();
	kth_element(1, n, k);
	afisare();
	return 0;
}

void afisare()
{
	fout << a[k] << '\n';
}

int partition(int st, int dr)
{
	long long int pivot = a[st];
	int i = st, j = dr;

	while (i < j)
	{
		while (i < j && pivot <= a[j])
			j--;
		a[i] = a[j];

		while (i < j && pivot >= a[i])
			i++;
		a[j] = a[i];
	}

	a[i] = pivot;
	return i;
}

void kth_element(int st, int dr, int k)
{
	if (st < dr)
	{
		int pos;

		pos = partition(st, dr);

		if (pos == k)
		{
			afisare();
			exit(0);
		}
		else if (pos < k)
			kth_element(pos + 1, dr, k);
		else
			kth_element(st, pos - 1, k);
	}
}

void citire()
{
	fin >> n >> k;
	for (int i = 1; i <= n; i++)
		fin >> a[i];
}