Cod sursa(job #658928)

Utilizator blk.irineluIrina Ursateanu blk.irinelu Data 9 ianuarie 2012 20:00:28
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include<cstdlib>
#define MAXN 3000002

using namespace std;

ifstream f("sdo.in");
ofstream g("sdo.out");

int a[MAXN],n,k;

int part(int s,int d)
{
    int i=s-1,j=d+1,val=a[s +rand()%(d-s+1)];
    while(1)
    {
        do i++;
        while(a[i]<val);

        do j--;
        while(a[j]>val);
         if(i<j)
         {
             int aux=a[i];
             a[i]=a[j];
             a[j]=aux;
         }
         return j;
    }
}
void quick(int s,int d,int k)
{
    if(s==d) return;
    int m=part(s,d);
    int x;
    x=m-s+1;
    if(x>=k) quick(s,m,k);
    else quick(m+1,d,k-x);
}

int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++)
        f>>a[i];
     quick(1,n,k);
     g<<a[k]<<"\n";
    return 0;
}