Cod sursa(job #641958)
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<iostream>
#include<algorithm>
const int maxN=3000010;
using namespace std;
int v[maxN];
int part(int v[maxN],int st, int dr)
{
int poz,i,j;
i=st-1; j=dr+1;
poz=v[st+rand()%(dr-st+1)];
int da=1;
while(da)
{
while(v[i]<poz)
++i;
if(i==st-1)
i++;
while(poz<v[j])
--j;
if(j==dr+1)
j--;
if(i<j)
{
int jj=v[i];
v[i]=v[j];
v[j]=jj;
}
else
{
da=0;
return j;
}
}
return 0;
}
void bin(int v[maxN], int st, int dr, int k)
{
int x,y;
if(st==dr)
return;
x=part(v,st,dr);
y=x-st+1;
if(y>=k)
bin(v,st,x,k);
else bin(v,x+1,dr,k-y);
}
int main()
{
srand(time(NULL));
int n,k;
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]);
bin(v,1,n,k);
printf("%d\n",v[k]);
return 0;
}
/*
Aigis: Not...good...
*/