Cod sursa(job #964967)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 iunie 2013 20:32:37
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int a[3000005], N, K;

int poz( int left, int right )
{
    int m = -1;

    while( left < right )
    {
        if ( a[left] > a[right] )
        {
            swap( a[left], a[right] );
            m = -m;
        }

        if ( m == 1 )
            left++;
        else
            right--;
    }

    return left;
}

void sort(  int left, int right, int k )
{
    if ( left < right )
    {
        int q = poz( left, right );
        int t = q - left + 1;

        if( t >= k )
            sort ( left, q, k );
        else
            sort( q + 1, right, k - t );
    }
}

int main()
{
    ifstream f("sdo.in");
    ofstream g("sdo.out");

    f >> N >> K;

    string fileData( ( istreambuf_iterator<char> ( f ) ) , istreambuf_iterator < char > ( ) ) ;

    int l = fileData.length();
    int i, nr = 0, j = 0;

    for ( int i = 1; i < l; i++ )
    {
        if ( isspace( fileData[i] ) )
        {
            a[ ++j ] = nr;
            nr = 0;
            continue;
        }

        nr = nr * 10 + ( fileData[i] - '0' );
    }

    sort(1, N,K);

    g << a[K];

    return 0;
}