Cod sursa(job #1562347)

Utilizator iuliaotilia26Mustea Iulia-Otilia iuliaotilia26 Data 4 ianuarie 2016 23:39:35
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int a[3000001];
int n,k;
int qs(int v[],int st,int dr,int k)
{
    int nr,aux,i,j,piv;
    if(st==dr) return a[st];
    piv=v[rand()%(dr-st)+1+st];
    i=st;
    j=dr;
    while(i<=j)
    {
        while(v[i]<piv) i++;
        while(v[j]>piv) j--;
        if(i<=j)
        {
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            j--;
            i++;
        }
    }
    if(j-st+1>=k) return qs(v,st,j,k);
    return qs(v,j+1,dr,k-j+st-1);
}

int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++) f>>a[i];
    g<<qs(a,1,n,k);
    f.close();
    g.close();
    return 0;
}