Pagini recente » Borderou de evaluare (job #17529) | Cod sursa (job #606331)
Cod sursa(job #606331)
#include<fstream.h>
#define N 3000001
long n,a[N],i,k,j,t;
long pa(long a[N],long p,long r)
{long i=p-1,j,x=a[r],m;
for(j=p;j<r;j++)
if(a[j]<=x)
{i++;
if(i!=j&&a[i]!=a[j])
m=a[i],a[i]=a[j],a[j]=m;}
if(i+1!=r&&a[i+1]!=a[r])
m=a[i+1],a[i+1]=a[r],a[r]=m;
return i+1;}
long rp(long a[N],long p,long r)
{long m;
if((p+r)%2==0)
m=a[r],a[r]=a[p],a[p]=m;
return pa(a,p,r);}
long s(long a[N],long p,long r,long i)
{long q,k;
if(p==r)
return a[p];
q=rp(a,p,r);
k=q-p+1;
if(i==k)
return a[q];
else
if(i<k)
return s(a,p,q-1,i);
else
return s(a,q+1,r,i-k);}
int main()
{ifstream f("sdo.in");
ofstream g("sdo.out");
f>>n>>k>>a[1];
for(i=2;i<=n;i++)
{f>>a[i];
if(a[i-1]<a[i])
j++;
else
t++;}
if(j==n-1)
g<<a[k];
else
if(t==n-1)
g<<a[n-k+1];
else
g<<s(a,1,n,k);
return 0;}