Cod sursa(job #1866503)

Utilizator xtreme77Patrick Sava xtreme77 Data 3 februarie 2017 10:47:59
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std ;

int v [3000999] ;

ifstream cin ("sdo.in") ;
ofstream cout ("sdo.out") ;

int part ( int st , int dr ) 
{
	int pivot = v [ ( st + dr ) >> 1 ] ; 
	++ dr ;
	-- st ;
	while ( st < dr ) {
		do {
			++ st ;
		}while ( v [st] < pivot ) ; 
		do {
			-- dr ; 
		}while ( v [dr] > pivot ) ;
		if ( st < dr ) {
			swap (v[st], v [dr]) ;
		} 
	}
	return dr ;
}

void calc (int i, int j, int k) 
{
	if (i < j) {
		int p = part (i,j) ;
		if (k <= p - i + 1) {
			calc (i, p, k) ;
		}
		else {
			calc (p + 1, j, k - (p - i + 1)) ;
		}
	}
}

int main()
{
	int n , k ; 
	cin >> n >> k ; 
	for ( int i = 1 ; i <= n ; ++ i ) {
		cin >> v [i] ;
	}
	calc (1,n,k) ;
	cout << v[k] ; 
	return 0 ; 
}