Pagini recente » Cod sursa (job #894616) | Cod sursa (job #2490868) | Cod sursa (job #3164589) | Cod sursa (job #156038) | Cod sursa (job #1019196)
#include<fstream>
#include<cstdlib>
#define dim 500007
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int a[dim],n,i,k;
int pivotare(int st,int dr){
int i,j,piv;
i=st-1;
j=dr+1;
piv=a[st+rand()%(dr-st+1)];
while(3543231){
do{
++i;
}while(a[i]<piv);
do{
--j;
}while(a[j]>piv);
if(i<j)
swap(a[i],a[j]);
else
return j;
}
return 0;
}
void quick(int st,int dr,int k){
if(st<dr){
int pivot=pivotare(st,dr);
int dist=pivot-st+1;
if(dist>=k)
quick(st,pivot,k);
else
quick(pivot+1,dr,k-dist);
}
}
int main () {
f>>n>>k;
for(i=1;i<=n;++i)
f>>a[i];
quick(1,n,k);
g<<a[k]<<"\n";
return 0;
}