Cod sursa(job #373481)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 13 decembrie 2009 21:29:45
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
#include<time.h>
#include<cstdlib>
using namespace std;
int a[3000003];
int partition(int *a,int p,int r)
 {
 int x=a[r];
  int i=p-1;
  for(int j=p;j<=r;j++) if(a[j]<x) {i++;int aux=a[j];a[j]=a[i];a[i]=aux;}
   ;int aux2=a[r];a[r]=a[i+1];a[i+1]=aux2;
   return i+1;}
int quick(int *a,int p,int r,int k)   
{if(p<r)
  {int q=partition(a,p,r);
    int temp=q-p+1; 
    if(temp==k) return a[k];
    else if(temp<k) return quick(a,q+1,r,k-temp);
         else return quick(a,p,q-1,k);
        }
     }
int main()
{int n,k;
freopen("sdo.in","r",stdin);
freopen("sdo.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
quick(a,1,n,k);
printf("%d",a[k]);
    return 0;}