Cod sursa(job #1522811)

Utilizator sulzandreiandrei sulzandrei Data 11 noiembrie 2015 23:20:09
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");
int v[3000003];
int quickSortsdo( int st , int dr , int k)
{
    if( st == dr)
        return v[ st ];
    int i = st, j = dr;
    int pivot = v[ rand() % ( dr-st)+1+st ];
    while ( i <= j )
    {
        while( v[i] < pivot )
            i++;
        while( v[j] > pivot )
            j--;
        if( i<=j)
        {
            swap (v[i],v[j] );
            i++;
            j--;
        }
    }
    int dim = j-st+1;
    if (dim >= k) //daca dimensiunea intervalului e mai maare ca k atunci ne deplasam in stanga
        return quickSortsdo(st, j, k);
    return quickSortsdo(j+1, dr, k - dim);//altfel in dreapta si scadem din k dimensiunea
    }
struct greater1{
    bool operator()(const long& a,const long& b) const{
        return a>b;
    }
};
int main()
{
    int n,k;
    in >> n >> k;
    for(int i = 1 ; i <= n; i ++)
    {
        in >> v[i];
    }
    /*out<<quickSortsdo( 1 , n, k );*/
    /*make_heap(v+1 , v+n+1,greater1());
    for(int i = 0 ; i < k-1 ; i ++)
        pop_heap(v+1,v+1+n-i,greater1());
    out<<v[1];*/
    sort(v+1,v+1+n);
    out<<v[k];



    return 0;
}