Cod sursa(job #964973)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 iunie 2013 20:51:46
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

int a[3000005], N, K;

int poz( int l, int r )
{
    int i = l, j = r, pivot = a[ ( l + r ) / 2 ];

    while( true )
    {
        while( a[i] < pivot )
            i++;

        while( a[j] > pivot )
            j--;

        if ( i < j )
            swap( a[i], a[j] );
        else
            return j;
    }

    return 0;
}

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;

    for ( int i = 1; i <= N; i++ )
        f >> a[i];

    sort(1, N,K);

    g << a[K];

    return 0;
}