Pagini recente » Istoria paginii utilizator/laoonatic | Cod sursa (job #1291649) | Istoria paginii utilizator/anthraxzt | Istoria paginii utilizator/francishendrix1432 | Cod sursa (job #856987)
Cod sursa(job #856987)
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string.h>
using namespace std;
int v[300001],k,cont;
int n;
using namespace std;
int partitionare(int st,int dr)
{
int pivot,p,i,j,aux;
i=st-1;
j=dr+1;
p=st+(rand()%(dr-st+1));
pivot=v[p];
while(1)
{
do{ i++; } while(v[i]<pivot);
do{ j--; } while(v[j]>pivot);
if(i<j)
{
aux=v[i];
v[i]=v[j];
v[j]=aux;
}
else
return j;
}
}
void sort(int st,int dr,int k)
{
int partitie;
while(st!=dr)
{
partitie=partitionare(st,dr);
cont=partitie-st+1;
if (cont>=k)
st=partitie;
else
{ dr=partitie+1; k=k-cont; }
}
}
void read()
{
int i;
scanf("%d %d",&n,&k);
for (i=1;i<=n;++i)
scanf("%d",&v[i]);
}
int ck;
void write()
{
printf("%d",v[ck]);
}
int main()
{
freopen("sdo.in","r",stdin);
freopen("sdo.out","w",stdout);
read();
srand(time(NULL));
ck=k;
sort(1,n,k);
write();
}