Cod sursa(job #1871875)

Utilizator raduzxstefanescu radu raduzx Data 7 februarie 2017 18:31:34
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
long long v[10000003],output[10000003];
long long n;
typedef long long ll;
ll getmax()
{
    ll i,maxim=0;
    for(i=1;i<=n;i++)
    {
        if(maxim<v[i])
            maxim=v[i];
    }
    return maxim;
}
void afisare()
{
    for(ll i=1;i<=n;i+=10)
        g<<v[i]<<" ";
}
ll cifre[12];
void radix(ll exp)
{
    ll i;
    for(i=0;i<=9;i++)
        cifre[i]=0;
    for(i=1;i<=n;i++)
        cifre[(v[i]/exp)%10]+=1;
    for(i=1;i<=9;i++)
        cifre[i]+=cifre[i-1];
    for(i=n;i>=1;i--)
    {
        output[cifre[(v[i]/exp)%10]-1]=v[i];
        cifre[(v[i]/exp)%10]-=1;
    }
    for(i=1;i<=n;i++)
        v[i]=output[i];
}
int main()
{
    ll a,b,c,exp,i,maxim;
    f>>n>>a>>b>>c;
    v[1]=b;
    for(i=2;i<=n;i++)
        v[i]=(a*v[i-1]+b)%c;
    maxim=getmax();
    for(exp=1;maxim/exp>0;exp*=10)
        radix(exp);
    afisare();
    f.close();
    g.close();
    return 0;
}