Cod sursa(job #1517208)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 3 noiembrie 2015 22:52:26
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

unsigned int n;
unsigned int a;
unsigned int b;
unsigned int c;

fstream fout;

void CreateList(vector<unsigned int> &numbers)
{
    numbers.push_back(b);
    for (unsigned int k = 1;k < n;k += 1)
    {
        unsigned long long v1 = ((unsigned long long)(a)) * numbers.back() + b;
        numbers.push_back(v1 % c);
    }
}

void Sort(vector<unsigned int> &numbers,unsigned int level,unsigned int &counter)
{
    if (level == 3)
    {
        sort(&numbers.front(),&numbers.front() + numbers.size());
        for (unsigned int a = 0;a < numbers.size();a += 1,counter += 1)
        {
            if ((counter % 10) == 0)
            {
                fout << numbers[a] << " ";
            }
        }
        return;
    }

    vector<unsigned int> mininumbers[256];
    for (unsigned int a = 0;a < numbers.size();a += 1)
    {
        unsigned int value = numbers.at(a);
        mininumbers[(value >> ((3 - level) << 3)) & 0XFF].push_back(value);
    }

    for (unsigned int a = 0;a < 256;a += 1)
    {
        if (mininumbers[a].size() > 0)
        {
            Sort(mininumbers[a],level + 1,counter);
        }
    }
}

int main(void)
{
    fstream fin("radixsort.in",ios::in);
    fout.open("radixsort.out",ios::out);

    fin >> n >> a >> b >> c;

    vector<unsigned int> numbers;
    CreateList(numbers);

    unsigned int counter = 0;
    Sort(numbers,0,counter);

    fin.close();
    fout.close();

    return 0;
}