Cod sursa(job #1603824)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 februarie 2016 19:37:34
Problema Statistici de ordine Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <ctime>
#define N 3000009
using namespace std;
int n, k, a[N];
int quickSort(int left, int right)
{
	int mid = left + (rand()%(right - left+1)) ;
	int swapedElement = a[mid];
 	int i = left, j = right ;
        while (1)
	{
		while (a[i] < swapedElement)
			i++;
		while (a[j] > swapedElement)
			j--;
		if (i < j)
			swap(a[i], a[j]);
		else
			return j;

	}
	return 0;
}
void stat(int left, int right, int k)
{
	if (left == right)
		return;
	int pivot_position = quickSort(left, right);
 	int dist =  pivot_position - left + 1;
	if (dist >= k)
		stat(left, pivot_position, k);
	else
		stat(pivot_position + 1, right, k - dist);
}
int main()
{
	srand(time(NULL));
	fstream f, g;
	f.open("sdo.in", ios::in);
	g.open("sdo.out", ios::out);
	f >> n >> k;
	int i;
	for (i = 1; i <= n; i++)
		f >> a[i];

	stat(1, n, k);

	g << a[k];
	return 0;
}