Cod sursa(job #980099)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 3 august 2013 22:01:18
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define Nmax 500002

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){

    const int n = A.size();


    std::vector<unsigned int> B(n+1);
    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, n;
    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];

    return 0;
}