Cod sursa(job #1525808)

Utilizator daneel95Holteiu Daniel-Ninel daneel95 Data 15 noiembrie 2015 16:44:31
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <cstdlib>

using namespace std;

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

int a[3000001],n,k;

int Stat_Ord(int a[],int st,int dr,int k)
{
    if(st==dr) return a[st];
    int i=st,j=dr,pivot=a[rand() % (dr-st)+1+st],nr,aux;
    while(i<=j)
    {
        while(a[i]<pivot) i++;
        while(a[j]>pivot) j--;
        if(i<=j)
        {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
            j--;
            i++;
        }
    }
    nr=j-st+1;
    if(nr>=k) return Stat_Ord(a,st,j,k);
        else return Stat_Ord(a,j+1,dr,k-nr);
}
int main()
{
    int i;
    in>>n>>k;
    for(i=1;i<=n;i++) in>>a[i];
    out<<Stat_Ord(a,1,n,k);
    in.close();
    out.close();
    return 0;
}