Cod sursa(job #1603844)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 februarie 2016 19:48:01
Problema Statistici de ordine Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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  g;
	FILE *f;
	f=fopen("sdo.in","rt");
	g.open("sdo.out", ios::out);
    fscanf(f,"%d%d",&n,&k);
	int i;
	for (i = 1; i <= n; i++)
		fscanf(f,"%d",&a[i]);

	stat(1, n, k);

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