Cod sursa(job #978456)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 iulie 2013 20:13:36
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.85 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define Nmax 500002

int v[Nmax], n;

void ShellSort( int *a, int n )
{
    int h, i, j, k;

    for ( h = n; h; h >>= 1 )
            for ( i = h; i <= n; i++ )
            {
                k = a[i];

                for ( j = i; j >= h && k < a[j - h]; j -= h )
                    a[j] = a[j - h];

                a[j] = k;
            }
}

void ShellSort1( int *a, int n )
{
    for ( int increment = n >> 1; increment > 0; increment >>= 1 )
            for ( int i = increment; i <= n; i++ )
            {
                int temp = a[i];
                int j;

                for ( j = i; j >= increment; j -= increment )
                {
                    if ( temp < a[j - increment] )
                            a[j] = a[j - increment];
                    else
                            break;
                }

                a[j] = temp;
            }
}

void RadixSort( int *a, int n )
{
    int b[Nmax], bucket[10], m = a[1], exp = 1;

    for ( int i = 0; i < n; i++ )
            if ( a[i] > m )
                m = a[i];

    while( m / exp > 0 )
    {
        for ( int i = 0; i <= 9; i++ )
                bucket[i] = 0;

        for ( int i = 0; i < n; i++ )
                bucket[(a[i]/exp)%10]++;

        for ( int i = 1; i < 10; i++ )
                bucket[i] += bucket[i - 1];

        for ( int i = n - 1; i >= 0; i-- )
                b[--bucket[(a[i]/exp)%10]] = a[i];

        for ( int i = 0; i < n; i++ )
                a[i] = b[i];

        exp *= 10;
    }
}

static const unsigned int digits = 2;        //Digits
static const unsigned int r = 16;                 //Bits
static const unsigned int radix = 1 << r;         //Bins
static const unsigned int mask = radix - 1;

void radix_sort(std::vector<int>& A){

    std::vector<unsigned int> B(n);
    std::vector<unsigned int> cnt(radix);

    for(unsigned int i = 0, shift = 0; i < digits; i++, shift += r){
        for(unsigned int j = 0; j < radix; ++j){
            cnt[j] = 0;
        }

        for(unsigned int j = 0; j < n; ++j){
            ++cnt[(A[j] >> shift) & mask];
        }

        for(unsigned int j = 1; j < radix; ++j){
            cnt[j] += cnt[j - 1];
        }

        for(long j = n - 1; j >= 0; --j){
            B[--cnt[(A[j] >> shift) & mask]] = A[j];
        }

        for(unsigned int j = 0; j < n; ++j){
           A[j] = B[j];
        }
    }
}

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

    int k;
    f >> n >> k;

    vector<int> A;

    for ( int i = 0, a; i < n; i++ )
            f >> a,
            A.push_back( a );

    radix_sort(A);

    g << A[k-1];

    //for ( int i = 0; i < n; i++ )
            //g << A[i] << " ";

    return 0;
}