Cod sursa(job #526692)
#include<iostream.h>
#include<fstream.h>
#define N 3000001
long n,a[N],i,k;
long partition(long a[N],long p,long r)
{long i=p-1,j,x=a[r],m;
for(j=p;j<r;j++)
if(a[j]<=x)
{i++;
if(i!=j)
{m=a[i];
a[i]=a[j];
a[j]=m;}}
if(i+1!=r)
{m=a[i+1];
a[i+1]=a[r];
a[r]=m;}
return i+1;}
long randomized_partition(long a[N],long p,long r)
{long aux;
if((p+r)%2==0)
{aux=a[r];
a[r]=a[p];
a[p]=aux;}
return partition(a,p,r);}
long select(long a[N],long p,long r,long i)
{if(p==r)
return a[p];
long q=randomized_partition(a,p,r),k;
k=q-p+1;
if(i==k)
return a[q];
else
if(i<k)
return select(a,p,q-1,i);
else
return select(a,q+1,r,i-k);}
int main()
{ifstream f1("sdo.in");
ofstream f2("sdo.out");
f1>>n>>k;
for(i=1;i<=n;i++)
f1>>a[i];
f2<<select(a,1,n,k);
f1.close();
f2.close();
return 0;}