Pagini recente » Cod sursa (job #1844475) | Cod sursa (job #349998) | Istoria paginii runda/eusebiu_oji_2012_cls9/clasament | Cod sursa (job #1591770) | Cod sursa (job #2749104)
#include <bits/stdc++.h>
#define int long long int
#define NMAX 3000009
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
int n,k;
int v[NMAX];
int partitionez(int st, int dr)
{
int i,j;
int aux;
int el_rand= st+ rand()% (dr-st);
swap( v[el_rand], v[st]);
aux= v[st];
i=st+1;
j=dr;
while(i<=j)
{
if( v[i]<=aux)
i++;
if(v[j]>=aux)
j--;
if(i<j && v[i]>aux && v[j]<aux)
{
swap(v[i],v[j]);
i++;
j--;
}
}
int where=i-1;
v[st]=v[where];
v[where]=aux;
return where;
}
void quicksort( int * v, int st, int dr)
{
if(st+1>=dr) return;
int poz= partitionez(st,dr);
if( poz- st>=k)
quicksort(v,st,poz-1);
else
if(poz-st==k-1)
quicksort(v,poz+1,dr );
}
int32_t main()
{
srand(time(NULL));
fin>>n>>k;
int i;
for(i=1;i<=n;i++)
fin>>v[i];
quicksort(v,1,n);
fout<<v[k]<<" ";
return 0;
}