Cod sursa(job #1631578)

Utilizator andreiudilaUdila Andrei andreiudila Data 5 martie 2016 17:09:19
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int n,k,a[3000001];
int i;
void nth (int l, int r)
{
    if(r-l+1<2)
    return ;

    int x=a[(l+r)/2];
    int i=l, j=r;

    do{
    while(a[i]<x)
        ++i;
    while(a[j]>x)
        --j;

    if(i<j){

    swap(a[i], a[j]);
    ++i;
    --j;
    }

    } while(i<j);

    if (j>=k) nth(l,j);
    else nth(j+1,r);
}

int main()
{
    fin>>n>>k;
    for(i=1;i<=n;++i)
        fin>>a[i];

    a[n+1]=2000000000;

    nth(1,n);

    fout<<a[k];
    return 0;
}