Cod sursa(job #1659403)

Utilizator danstefanDamian Dan Stefan danstefan Data 22 martie 2016 10:42:26
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;
int n,k,i,v[3000011];
void Answer(int l,int r)
{
    if(l<r)
    {
        int in=l;
        int sf=r;
        swap(v[r],v[in+rand()%(sf-in+1)]);
        int   p=v[r];
        int   j=in-1;
        for(i=in; i<=sf; ++i)
            if(v[i]<=p)swap(v[++j],v[i]);
        if(j>k)Answer(l,j-1);
        else Answer(j+1,r);
    }
}
int main()
{
    freopen("sdo.in","r",stdin);
    freopen("sdo.out","w",stdout);
    srand(time(0));
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; ++i)
        scanf("%d",&v[i]);
    Answer(1,n);
    printf("%d\n",v[k]);
    return 0;
}