Cod sursa(job #1517218)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 3 noiembrie 2015 23:02:38
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 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);
    }
}

vector<unsigned int> final;

void Sort(vector<unsigned int> &numbers,unsigned int level,unsigned int &counter)
{
    if (level == 3)
    {
        for (int a = 0;a < 256;a += 1)
        {
            final[a] = 0;
        }
        for (int a = 0;a < numbers.size();a += 1)
        {
            final[numbers[a] & 0XFF] += 1;
        }
        unsigned int prefix = numbers[a] & ~0XFF;
        for (unsigned int a = 0;a < final.size();a += 1)
        {
            int count = final.at(a);
            int nextCounter = counter + count;

            for (int b = 0;b < nextCounter / 10;b += 1)
            {
                fout << (prefix | a) << " ";
            }

            counter = nextCounter % 10;
        }
        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;

    final.resize(256,0);

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

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

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

    return 0;
}