Cod sursa(job #2119814)

Utilizator cipri321Marin Ciprian cipri321 Data 1 februarie 2018 17:49:15
Problema Statistici de ordine Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#define DIM 3000001
using namespace std;
ifstream fi("sdo.in");
ofstream fo("sdo.out");
int n,k;
int A[DIM];
int part(int st,int dr)
{
    int i=st-1,j=dr+1,pivot=A[st+(rand()%(dr-st+1))];
    while(true)
    {
        do
        {
            i++;
        }while(A[i]<pivot);
        do
        {
            j--;
        }while(A[j]>pivot);
        if(i>=j)
            return j;
        swap(A[i],A[j]);
    }
}
void jmen(int st,int dr,int k)
{
    if(st==dr)
        return ;
    int p=part(st,dr),c=p-st+1;
    if(c>=k)
        jmen(st,p,k);
    else
        jmen(p+1,dr,k-p);
}
int main()
{
    fi>>n>>k;
    for(int i=1;i<=n;i++)
        fi>>A[i];
    srand(time(NULL));
    jmen(1,n,k);
    fo<<A[k];
    fi.close();
    fo.close();
    return 0;
}