Cod sursa(job #2258533)

Utilizator ianiIani Biro iani Data 11 octombrie 2018 17:04:54
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 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;

/*int maxsir()
{
    unsigned int maxi=sir[1];
    for (int i=2; i<=n; i++)
        if (maxi<sir[i])
            maxi=sir[i];
    return maxi;
}*/

void countingsort(int put)
{
    int apcif[10];

    for (int i=0; i<=9; i++)
        apcif[i]=0;

    for (int i=1; i<=n; i++)
        apcif[sir[i]/put%10]++;
    for (int i=1; i<=9; i++)
        apcif[i]+=apcif[i-1];
    for (int i=n; i>=1; i--)
    {
        out[apcif[sir[i]/put%10]]=sir[i];
        --apcif[sir[i]/put%10];
    }
    for (int i=1; i<=n; i++)
        sir[i]=out[i];
}

void radixsort(unsigned int maxi)
{
    for (unsigned int put=1; maxi/put>0; put*=10)
        countingsort(put);
}

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;
}