Cod sursa(job #526707)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 ianuarie 2011 11:39:38
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<iostream.h>
#include<fstream.h>
#define N 3000001
long n,a[N],i,k,j,t;

long partition(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 randomized_partition(long a[N],long p,long r)
{long aux;
if((p+r)%2==0)
       {aux=a[r];
       a[r]=a[p];
       a[p]=aux;}
return partition(a,p,r);}

long select(long a[N],long p,long r,long i)
{long q,k;
if(p==r)
        return a[p];
q=randomized_partition(a,p,r);
k=q-p+1;
if(i==k)
        return a[q];
else
        if(i<k)
                 return select(a,p,q-1,i);
        else
                 return select(a,q+1,r,i-k);}

int main()
{ifstream f1("sdo.in");
ofstream f2("sdo.out");
f1>>n>>k>>a[1];
j=0;
t=0;
for(i=2;i<=n;i++)
     {f1>>a[i];
     if(a[i-1]<a[i])
            j++;
     else
            t++;}
if(j==n-1)
     f2<<a[k];
else
     if(t==n-1)
            f2<<a[n-k+1];
     else
            f2<<select(a,1,n,k);
f1.close();
f2.close();
return 0;}