Cod sursa(job #2462527)

Utilizator paul_danutDandelion paul_danut Data 27 septembrie 2019 15:17:43
Problema Statistici de ordine Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>

constexpr int countsize = 256;
constexpr int bucketsize = 8;
constexpr int mask = (1 << bucketsize) - 1;

int computeIndex(int val, int bucket)
{
	return val >> (bucket * bucketsize) & mask;
}

std::vector<int> computeFrequencies(const std::vector<int>& input, int bucket)
{
    std::vector<int> frequence(countsize, 0);

    for (auto it = input.cbegin(); it != input.cend(); ++it)
    {
        auto c = computeIndex(*it, bucket);
        frequence[c]++;
    }

    return frequence;
}

std::vector<int> computePositions(const std::vector<int>& frequence)
{
    std::vector<int> index(countsize, 0);
    int i, count = frequence[0];

    for (i = 1; i < countsize; i++)
    {
        if (frequence[i])
        {
            index[i] = count;
            count += frequence[i];
        }
    }

    return index;
}

std::vector<int> moveElements(const std::vector<int>& input, std::vector<int>& frequence, std::vector<int>& index, int bucket)
{
    std::vector<int> temp(input.size(), 0);

    for (auto it = input.cbegin(); it != input.cend(); ++it)
    {
        auto pos = computeIndex(*it, bucket);
        frequence[pos] --;
        temp[index[pos]] = *it;
        index[pos]++;
    }

    return temp;
}

void radixSort(std::vector<int>& input)
{
	for (auto bucket = 0; bucket < 4; bucket++)
	{
        auto frequence = computeFrequencies(input, bucket);
        auto index = computePositions(frequence);
        input = moveElements(input, frequence, index, bucket);
	}
}

int main()
{
    std::ifstream fin("sdo.in");
    std::ofstream fout("sdo.out");
    int n=0, k=0, i=0, x=0;
    fin>>n>>k;

    std::vector<int> v;
    for(i=0; i<n ; ++i){
        fin>>x;
        v.push_back(x);
    }

    radixSort(v);
    fout<<v[k-1];

    return 0;
}