Cod sursa(job #2258525)

Utilizator ianiIani Biro iani Data 11 octombrie 2018 16:50:39
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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()
{
    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()
{
    int maxi=maxsir();

    for (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;
    for (int i=2; i<=n; i++)
        sir[i]=(1LL*a*sir[i-1]+b)%c;
    radixsort();
    afisare();
    return 0;
}