Pagini recente » Cod sursa (job #394763) | Cod sursa (job #3162023) | Cod sursa (job #167043) | Cod sursa (job #1334392) | Cod sursa (job #659114)
Cod sursa(job #659114)
#include <iostream>
#include <fstream>
#include<cstdlib>
#define MAXN 3000002
using namespace std;
ifstream f("sdo.in");
ofstream g("sdo.out");
int v[MAXN],n,k;
int part(int left,int right)
{
int i=left-1,j=right+1,val=v[left +rand()%(right-left+1)];
while(1)
{ do
i++;
while(v[i]<val);
do j--;
while(v[j]>val);
if(i<j)
swap(v[i],v[j]);
else
return j;
}
}
void quick(int left,int right,int k)
{
if(left==right) return;
int m=part(left,right);
int x;
x=m-left+1;
if(x>=k) quick(left,m,k);
else quick(m+1,right,k-x);
}
int main()
{
f>>n>>k;
for(int i=1;i<=n;i++)
f>>v[i];
quick(1,n,k);
g<<v[k]<<"\n";
return 0;
}