Pagini recente » Cod sursa (job #2110356) | Cod sursa (job #1110450) | Cod sursa (job #73784) | Istoria paginii utilizator/b0by.ceausu | Cod sursa (job #1965596)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
using namespace std;
const int INF=2140e6;
const int MaxN=1e2+5;
FILE *IN,*OUT;
int N,K;
long long v[MaxN];
long long Partition(long long *s,int start,int end,int &piv)
{
int index=start;
piv=s[start+rand()%(end-start+1)];
for(int i=start;i<=end;i++)
if(v[i]<=piv)
swap(v[i],v[index++]);
return index-1;
}
long long N_th_Element(long long *s,int start,int end,int k)
{
int piv;
int index=Partition(s,start,end,piv);
if(index-start+1==k)
return piv;
else if(index-start+1>k)
return N_th_Element(s,start,index,k);
else if(index-start+1<k)
return N_th_Element(s,index+1,end,k-index+start-1);
}
int main()
{
IN=fopen("sdo.in","r");
OUT=fopen("sdo.out","w");
srand(time(NULL));
fscanf(IN,"%d%d",&N,&K);
for(int i=1;i<=N;i++)
fscanf(IN,"%lld",&v[i]);
fprintf(OUT,"%lld\n",N_th_Element(v,1,N,K));
return 0;
}