Cod sursa(job #2061112)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 8 noiembrie 2017 22:14:31
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int nmax=3000000;
int ve[nmax+5];
int quicks(int v[],int st,int dr,int k)
{
    if(st==dr)
        return v[st];
    int piv=v[(rand()%(dr-st+1))+st];
    int poz=st-1;
    int i,nrp=0,ps;
    for(i=st; i<=dr; i++)
        if(v[i]<=piv)
        {
            poz++;
            swap(v[poz],v[i]);
        }
    ps=poz;
    for(i=poz; i>=st; i--)
        if(v[i]==piv)
        {
            swap(v[i],v[ps]);
            nrp++;
            ps--;
        }
    if(poz<k)
    {
        return quicks(v,poz+1,dr,k);
    }
    else
    {
        if(poz-nrp<k)
            return piv;
        else
        {
            return quicks(v,st,ps,k);
        }
    }
}
int main()
{
    freopen("sdo.in","r",stdin);
    freopen("sdo.out","w",stdout);
    int n,k,i,j;
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; i++)
        scanf("%d",&ve[i]);
    printf("%d\n",quicks(ve,1,n,k));
    return 0;
}