Pagini recente » Cod sursa (job #66853) | Cod sursa (job #478873) | Cod sursa (job #372207) | Cod sursa (job #1823974) | Cod sursa (job #658928)
Cod sursa(job #658928)
#include <iostream>
#include <fstream>
#include<cstdlib>
#define MAXN 3000002
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int a[MAXN],n,k;
int part(int s,int d)
{
int i=s-1,j=d+1,val=a[s +rand()%(d-s+1)];
while(1)
{
do i++;
while(a[i]<val);
do j--;
while(a[j]>val);
if(i<j)
{
int aux=a[i];
a[i]=a[j];
a[j]=aux;
}
return j;
}
}
void quick(int s,int d,int k)
{
if(s==d) return;
int m=part(s,d);
int x;
x=m-s+1;
if(x>=k) quick(s,m,k);
else quick(m+1,d,k-x);
}
int main()
{
f>>n>>k;
for(int i=1;i<=n;i++)
f>>a[i];
quick(1,n,k);
g<<a[k]<<"\n";
return 0;
}