Cod sursa(job #1740919)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 12 august 2016 15:10:58
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstring>

#define BYTE 0xff+1
#define getByte(X,Y) (*(((unsigned char *)&X)+Y))//x=source y=whichByte
#define NR_BYTES (sizeof(uint32_t))

using namespace std;

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

uint32_t n,v[10000005];


void generatenum(uint32_t a,uint32_t b,uint32_t c)
{
    v[0]=b%c;
    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 countsort(uint32_t v1[],uint32_t v2[],uint32_t i)
{uint32_t counter[BYTE], index[BYTE];
    memset(counter, 0, sizeof(counter));
    for(uint32_t j = 0; j < n; ++j) counter[ getByte(v1[j],i) ]++;
    index[0] = 0;
    for(uint32_t j = 1; j < BYTE; ++j) index[j] = index[j - 1] + counter[j - 1];
    for(uint32_t j = 0; j < n; ++j)
    v2[ index[ getByte(v1[j],i) ]++ ] = v1[j];}

void magic()
{uint32_t *temp = new uint32_t[n];
for (uint32_t i=0;i<NR_BYTES;++i)
if (i%2==0)
countsort(v,temp,i);
else
countsort (temp,v,i);

reveal();
}

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