Cod sursa(job #2202892)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 10 mai 2018 12:29:01
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#define nmax 3000005
#include <fstream>
#include <stdlib.h>
using namespace std;
int n, k, a[nmax];
fstream f1("sdo.in", ios::in);
fstream f2("sdo.out", ios::out);
int part(int st, int dr)
{
    int i, j, piv=a[rand()%(dr-st+1)+st];
    i=st-1; j=dr+1;
    while(1)
    {
        do{i++;} while(a[i]<piv);
        do{j--;} while(a[j]>piv);
        if(i<j) swap(a[i], a[j]);
        else return j;
    }
    return -1;
}
void cauta(int st, int dr, int k)
{
    if(st==dr) ;
    else
    {
        int piv=part(st, dr);
        if(k<= (piv-st+1)) cauta(st, piv, k);
        else  cauta(piv+1, dr, k-(piv-st+1));
    }
}
int main()
{
    int i;
    f1>>n>>k;
    for(i=1; i<=n; i++) f1>>a[i];
    cauta(1, n, k);
    f2<<a[k];
    return 0;
}