Cod sursa(job #772163)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 28 iulie 2012 14:49:15
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<cstdlib>
using namespace std;

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

int n,k,i,a[30001];

void qsrt(int li, int lf, int p)
{int d;
 d=lf-li+1;
 if(d>1)
 {int b[30001];
 int r;
 r=li+rand()%d;
 int si=0, sf=0;
 for(int j=li; j<=lf; j++)
   {if(a[j]<a[r])
      {si++;
      b[si]=a[j];}
    if(a[j]>a[r])
      {sf++;
       b[d+1-sf]=a[j];}
    }
 b[si+1]=a[r];
 for(int j=li; j<=lf; j++)
     a[j]=b[j-li+1];
 if(si+1>p)    
  qsrt(li,si,p);
 if(si+1<p)
  qsrt(si+2,lf,p-si-1);     
 } 
}

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