Cod sursa(job #1058032)

Utilizator caen1c a e n caen1 Data 14 decembrie 2013 23:08:26
Problema Statistici de ordine Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.03 kb
#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;
}