Pagini recente » Cod sursa (job #2119872) | Cod sursa (job #1415483) | Cod sursa (job #1408112) | Cod sursa (job #1668647) | Cod sursa (job #1195551)
#include <cstdio>
using namespace std;
#define MAX 3000001
int v[MAX], n, k;
int kthelem(int st, int dr);
int main()
{
int i;
freopen("sdo.in", "r", stdin);
freopen("sdo.out", "w", stdout);
scanf("%d%d", &n, &k);
for(i=1; i<=n; i++)
scanf("%d", v+i);
printf("%d", kthelem(1, n));
}
int kthelem(int st, int dr)
{
int piv=v[(st+dr)/2], mici=st, mari=dr, i=st, j=dr, a, b;
while(i<=j){
while(i<=dr and v[i]<=piv){
if(v[i]<piv) v[mici++]=v[i];
i++;
}
while(j>=st and v[j]>=piv){
if(v[j]>piv) v[mari--]=v[j];
j--;
}
if(i<j){
a = v[i]; b = v[j];
v[mici++]=b;
v[mari--]=a;
i++;
j--;
}
}
/*
for(i=st; i<=dr; i++) printf("%d ", v[i]);
printf("\n%d\n", piv);
for(i=st; i<mici; i++) printf("%d ", v[i]);
printf("!!");
for(i=mari+1; i<=dr; i++) printf("%d ", v[i]);
printf("\n");
*/
if(mici<=k and k<=mari) return piv;
if(mici>k) return kthelem(st, mici-1);
if(k>mari) return kthelem(mari+1, dr);
}