Pagini recente » Cod sursa (job #2861873) | Cod sursa (job #1083154) | Cod sursa (job #1058032)
#include <stdio.h>
#include <stdlib.h>
#define IN "sdo.in"
#define OUT "sdo.out"
#define NMAX 300000
static long A[NMAX + 1];
long partition(long start, long end)
{
long i, j, pivot, aux;
pivot = start + rand() % (end - start + 1);
for (i = j = start; j <= end; j++)
if (A[j] <= A[pivot]) {
aux = A[j];
A[j] = A[i];
A[i] = aux;
i++;
}
aux = A[i];
A[i] = A[pivot];
A[pivot] = A[i];
return i;
}
long order_statistic(long i, long j, long k)
{
long q, t;
if (i == j)
return A[i];
q = partition(i, j);
t = q - i + 1;
if (t == k)
return A[q];
else if (k < t)
return order_statistic(i, q - 1, k);
else
return order_statistic(q + 1, j, k - t);
}
int main(void)
{
long n, k, i;
freopen(IN, "r", stdin);
freopen(OUT, "w", stdout);
scanf("%ld %ld", &n, &k);
for (i = 1; i <= n; i++)
scanf("%ld", &A[i]);
printf("%ld\n", order_statistic(1, n, k));
return 0;
}