Cod sursa(job #462332)

Utilizator BitOneSAlexandru BitOne Data 10 iunie 2010 14:59:14
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define MAX_N 3000011

/*
 *
 */
using namespace std;
int v[MAX_N];
inline int MedianOf3( int left, int middle, int right )
{
    if( v[left] > v[right] )
        swap( v[left], v[right] );
    if( v[left] > v[middle] )
        swap( v[left], v[middle] );
    if( v[middle] < v[right] )
        swap( v[middle], v[right] );
    return v[right];
}
inline void OrderStatistic( int left, int right, int k )
{
    if( left < right )
    {
        srand( time(NULL) );
        int middle=left+(right-left)/2, lleft=left-1, rright=right+1, pValue=v[ left+rand()%(right-left+1) ];
        while( true )
        {
            while( lleft <= right &&  pValue > v[++lleft] );
            while( rright >= left && pValue < v[--rright] );
            if( lleft > rright )
                break;
            swap( v[lleft], v[rright] );
        }
        if( rright >= k )
            OrderStatistic( left, rright, k  );
        OrderStatistic( rright+1, right, k );
    }
}
int main( void )
{
    int N, k;
    ifstream in( "sdo.in" );
    in>>N>>k;
    copy( istream_iterator<int>(in), istream_iterator<int>(), v+1 );
    ofstream out( "sdo.out" );
    OrderStatistic( 1, N, k );
    out<<v[k]<<'\n';
    return EXIT_SUCCESS;
}