Pagini recente » Cod sursa (job #870675) | Cod sursa (job #2197085) | Cod sursa (job #342313) | Cod sursa (job #1094682) | Cod sursa (job #373248)
Cod sursa(job #373248)
#include <fstream>
using namespace std;
const int NMAX=3000003;
int N,K,x[NMAX];
int kth(int l,int r,int k)
{
if (l==r) return x[l];
int i=l,j=r,piv=x[l+rand()%(r-l+1)];
do
{
while (x[i]<piv) ++i;
while (x[j]>piv) --j;
if (i<=j)
{
int t=x[i];x[i]=x[j];x[j]=t;
++i;--j;
}
}while (i<=j);
if (j-l+1>=k) return kth(l,j,k);
return kth(j+1,r,k-j+l-1);
}
int main()
{
int i;
ifstream f("sdo.in");
ofstream g("sdo.out");
f>>N>>K;
for (i=1;i<=N;++i) f>>x[i];
g<<kth(1,N,K);
return 0;
}