Cod sursa(job #1517205)

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

#include <fstream>
#include <vector>

using namespace std;

unsigned long long n;
unsigned long long a;
unsigned long long b;
unsigned long long c;

fstream fout;

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

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

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

    for (unsigned long long 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 long long> numbers;
    CreateList(numbers);

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

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

    return 0;
}