Cod sursa(job #2269052)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 25 octombrie 2018 18:00:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 10000005;

queue <int> q[10];
int v[NMAX],v2[NMAX];

int main()
{
    int n,a,b,c;
    fin >> n >> a >> b >> c;
    int x;
    v[1]=b;
    int maxim=v[1];
    for(int i=1;i<=n;i++)
    {
        v[i]=(a*v[i-1]+b)%c;
        v2[i]=v[i];
        maxim=max(maxim,v[i]);
    }
    /*for(int i=2;i<=n;i++)
    {
        v[i]=(a*v[i-1]*b)%c;
        maxim=max(maxim,v[i]);
    }
    */
    int putere=0;
    int aux=maxim;
    while(aux!=0)
    {
        aux/=10;
        putere++;
    }
    int p=1;
    int k=0;
    int cifra=0;
    for(int i=1;i<=putere;i++)
    {
        k=0;
        for(int j=1;j<=n;j++)
        {
            cifra=(v2[j]/p)%10;
            q[cifra].push(v2[j]);
        }
        for(int j=0;j<=9;j++)
        {
            while(!q[j].empty())
            {
                v2[++k]=q[j].front();
                q[j].pop();
            }
        }
        /*for(int j=1;j<=k;j++)
        {
            fout << v2[j] << ' ';
        }
        fout << '\n';
        */
        p*=10;
    }
    for(int i=1;i<=n;i+=10)
    {
        fout << v2[i] << ' ';
    }
    return 0;
}