Cod sursa(job #659377)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 10 ianuarie 2012 16:28:25
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<cstdio>
#include<cstdlib>
using namespace std;

int a[3000001], N, K;

int partition(int lf, int rt){
	int i = lf - 1, j = rt + 1, val = a[ lf + rand() % ( rt - lf + 1 ) ], sw = 1;
	while(sw){
		while(a[++i] < val);
		while(val < a[--j]);
		if(i < j) a[i] = a[i] + a[j] - (a[j] = a[i]);
		else return j;
	}
}

void quick(int lf, int rt, int k){
	if(lf == rt) return;

	int div = partition(lf, rt), t = div - lf + 1;
	if(t >= k) quick(lf, div, k);
	else quick(div + 1, rt, k - t);
}

int main(){
	int i;
	freopen ("sdo.in", "r", stdin), freopen("sdo.out", "w", stdout);
	scanf("%d %d", &N, &K);
	for(i = 1; i <= N; i++)
		scanf("%d", &a[i]);
	
	quick(1, N, K);
	
	printf("%d\n", a[K]);
	return 0;
}