Cod sursa(job #2258992)

Utilizator ianiIani Biro iani Data 12 octombrie 2018 19:24:20
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

#define NMAX 10000005

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

unsigned int sir[NMAX],out[NMAX];
int n;

void countingsort(int byte)
{
    int apcif[256];
    
    for (int i=0; i<=255; i++)
        apcif[i]=0;
    
    for (int i=1; i<=n; i++)
        apcif[(sir[i]>>(byte*8))&255]++;
    for (int i=1; i<=255; i++)
        apcif[i]+=apcif[i-1];
    for (int i=n; i>=1; i--)
    {
        out[apcif[(sir[i]>>(byte*8))&255]]=sir[i];
        --apcif[(sir[i]>>(byte*8))&255];
    }
    for (int i=1; i<=n; i++)
        sir[i]=out[i];
}

void radixsort(unsigned int maxi)
{
    for (unsigned int byte=0; byte<4; byte++)
        countingsort(byte);
}

void afisare()
{
    for (int i=1; i<=n; i+=10)
        fout<<sir[i]<<' ';
}

int main()
{
    int a,b,c;
    fin>>n>>a>>b>>c;
    sir[1]=b;
    unsigned int maxi=b;
    for (int i=2; i<=n; i++)
    {
        sir[i]=(1LL*a*sir[i-1]+b)%c;
        if (sir[i]>maxi)
            maxi=sir[i];
    }
    radixsort(maxi);
    afisare();
    return 0;
}