Cod sursa(job #1420029)

Utilizator Alex1199Alex Bercea Alex1199 Data 17 aprilie 2015 13:06:11
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <ctime>
long int a[3000000];
long int n, k;
FILE *f=fopen("sdo.in","r");
FILE *g=fopen("sdo.out","w");
long int partition( long int p, long int r)
{
    long int pivot = a[p+rand()%(r-p+1)];

    while ( p < r )
    {
        while ( a[p] < pivot )
            p++;

        while ( a[r] > pivot )
            r--;

        if ( a[p] == a[r] )
            p++;
        else if ( p < r )
        {
            long int tmp = a[p];
            a[p] = a[r];
            a[r] = tmp;
        }
    }

    return r;
}
long int Select(long int p,long int r, long int i)
{
    if (p==r) return a[p];
    long int q=partition(p,r);
    k=q-p+1;
    if (i<=k) return Select(p,q,i);
         else     return Select(q+1,r,i-k);
}
int main()
{
    fscanf(f,"%ld%ld",&n,&k);
    for(int i=0; i<n; i++)
    {
        fscanf(f,"%ld",&a[i]);
    }
    fprintf(g,"%ld",Select(0,n-1,k));
    return 0;
}