Cod sursa(job #373248)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 13 decembrie 2009 03:14:52
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;
const int NMAX=3000003;
int N,K,x[NMAX];
int kth(int l,int r,int k)
{
    if (l==r) return x[l];
    int i=l,j=r,piv=x[l+rand()%(r-l+1)];
    do
    {
        while (x[i]<piv) ++i;
        while (x[j]>piv) --j;
        if (i<=j) 
        {
            int t=x[i];x[i]=x[j];x[j]=t;
            ++i;--j;
        }
    }while (i<=j);
    if (j-l+1>=k) return kth(l,j,k);
    return kth(j+1,r,k-j+l-1);
}
int main()
{
    int i;
    ifstream f("sdo.in");
    ofstream g("sdo.out");
    f>>N>>K;
    for (i=1;i<=N;++i) f>>x[i];
    g<<kth(1,N,K);
    return 0;
}