Cod sursa(job #1740902)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 12 august 2016 14:35:25
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 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,v1[10000005],v2[10000005];


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

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

void magic()
{   for (uint32_t i=0;i<NR_BYTES;++i){
    int 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];
    swap (v1,v2);}
    reveal();
}

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