Cod sursa(job #1740871)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 12 august 2016 13:33:14
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("radixsort.in");
ofstream t ("radixsort.out");

uint32_t n,v[10000000],bucket[256][500000],list[256];

void replace()
{
    uint32_t k=0;
    for (uint32_t i=0; i<256; ++i)
    {
        for (uint32_t j=0; j<list[i]; ++j,++k)
        {
            v[k]=bucket[i][j];
            bucket[i][j]=0;
        }
        list[i]=0;
    }
}

void place1(uint32_t x)
{
    uint32_t x1=x;
    x <<= 24;
    x >>= 24;
    bucket[x][list[x]]=x1;
    ++list[x];
}

void place2(uint32_t x)
{
    uint32_t x1=x;
    x <<= 16;
    x >>= 24;
    bucket[x][list[x]]=x1;
    ++list[x];
}

void place3(uint32_t x)
{
    uint32_t x1=x;
    x <<= 8;
    x >>= 24;
    bucket[x][list[x]]=x1;
    ++list[x];
}

void place4(uint32_t x)
{
    uint32_t x1=x;
    x >>= 24;
    bucket[x][list[x]]=x1;
    ++list[x];
}

void generatenum(uint32_t a,uint32_t b,uint32_t c)
{
    v[0]=b;
    for (uint32_t i=1; i<n; ++i)
        v[i]=(a*v[i-1]+b)%c;
}

void reveal()
{
    for (uint32_t i=0; i<n; i+=10)
        t<<v[i]<<" ";
}

void magic()
{
    for (uint32_t i=0; i<n; ++i)
        place1(v[i]);
    replace();
    for (uint32_t i=0; i<n; ++i)
        place2(v[i]);
    replace();
    for (uint32_t i=0; i<n; ++i)
        place3(v[i]);
    replace();
    for (uint32_t i=0; i<n; ++i)
        place4(v[i]);
    replace();
    reveal();
}

int main()
{
    uint32_t a,b,c;
    f>>n>>a>>b>>c;
    generatenum(a,b,c);
    magic();
    return 0;
}