Cod sursa(job #2308556)

Utilizator alexdumitrescuDumitrescu George Alex alexdumitrescu Data 27 decembrie 2018 12:52:02
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>

using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int n, v[2][10000005], lin1, lin2, a[10][12], s[10], maxx, k, aux, p, i, j, cif, A, B, C;
int main()
{
    fin >> n >> A >> B >> C;
    lin1=1;
    lin2=0;
    v[lin1][0]=B;
    aux=v[lin1][0];
    k=0;
    do
    {
        k++;
        a[k][aux%10+1]++;
        s[k]++;
        aux/=10;
    }
    while(aux!=0);
    maxx=k;
    for(i=1; i<n; i++)
    {
        v[lin1][i]=((long long)A*v[lin1][i-1]+B)%C;
        aux=v[lin1][i];
        k=0;
        do
        {
            k++;
            a[k][aux%10+1]++;
            s[k]++;
            aux/=10;
        }
        while(aux!=0);
        maxx=max(maxx, k);
    }
    p=1;
    for(i=1; i<=maxx; i++)
    {
        if(s[i]!=n)
            a[i][1]+=n-s[i];
        for(j=2; j<=10; j++)
            a[i][j]+=a[i][j-1];

        for(j=0; j<n; j++)
        {
            cif=v[lin1][j]/p%10+1;
            v[lin2][a[i][cif-1]]=v[lin1][j];
            a[i][cif-1]++;
        }
        swap(lin1, lin2);
        p=p*10;
    }
    for(i=0; i<n; i+=10)
        fout << v[lin1][i] << ' ';

    return 0;
}