Cod sursa(job #1522789)

Utilizator sulzandreiandrei sulzandrei Data 11 noiembrie 2015 23:04:41
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
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 ];
    srand( time( NULL ) );
    int i = st, j = dr;
    int position = st + rand() % ( dr-st+1);
    int pivot = v[ position ];
    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
}
int main()
{
    int n,k;
    in >> n >> k;
    for(int i = 1 ; i <= n; i ++)
    {
        in >> v[i];
    }
    out<<quickSortsdo( 1 , n, k );



    return 0;
}