Pagini recente » Cod sursa (job #2696255) | Cod sursa (job #1466651) | Cod sursa (job #2178500) | Cod sursa (job #3267860) | Cod sursa (job #2484389)
#include <bits/stdc++.h>
#define nmax 3000005
using namespace std;
int n, k, a[nmax];
int partitionn(int st, int dr){
int len = (dr - st + 1);
int wh = rand() % len;
swap(a[st],a[st+wh]);
int piv = a[st];
while (st < dr){
while (st < dr && a[dr] >= piv) --dr;
a[st] = a[dr];
while (st < dr && a[st] <= piv) ++st;
a[dr] = a[st];
}
a[st] = piv;
return st;
}
int di(int st, int dr){
if (st == dr){
if (st == k){
return a[k];
} else {
return -1;
}
}
int pos = partitionn(st, dr);
if (pos == k){
return a[k];
}
else if (pos > k){
return di(st,pos-1);
} else {
return di(pos+1,dr);
}
}
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",&a[i]);
}
printf("%d\n", di(1,n));
return 0;
}