Cod sursa(job #1255291)

Utilizator priestnoobFMI - Dan Nema priestnoob Data 4 noiembrie 2014 17:23:51
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define nmax 3000005

int n, k, v[nmax];

int pivot(int st, int dr)
{
    int y=st+(rand()%(dr-st))+1;
    int x=v[y];
    int q=st,w=dr;
    while(q<=w)
    {
        while(v[q]<x)
            q++;
        while(v[w]>x)
            w--;
        if(q<=w)
        {
            swap(v[q],v[w]);
            q++;
            w--;
        }
    }
    return w;
}

int element(int st, int dr, int k)
{
    if(st==dr)
        return (v[dr]);
    int q=pivot(st,dr);
    if(k>q)
        return(element(q+1,dr,k));
    else
        return (element(st,q,k));
}

int main()
{
    freopen("sdo.in","r",stdin);
    freopen("sdo.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%d",&v[i]);
    srand(10);
    printf("%d",element(1,n,k));
}