Cod sursa(job #1314029)

Utilizator eneandradaEne Oana-Andrada eneandrada Data 11 ianuarie 2015 14:23:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

int v[10000005],b[10000005],N,i,mx,exp=1;

void countsort(int v[], int N, int exp) //ordoneaza numerele dupa cifra (n/exp)%10
{
    int i,c[10]={0};
    for(i=1;i<=N;i++)
        c[(v[i]/exp)%10]=c[(v[i]/exp)%10]+1;
    for(i=1;i<=9;i++)
        c[i]=c[i]+c[i-1];
    for(i=N;i>=1;i--)
    {
        b[c[(v[i]/exp)%10]]=v[i];
        c[(v[i]/exp)%10]=c[(v[i]/exp)%10]-1;
    }
    for(i=1;i<=N;i++)
        v[i]=b[i];
}

void radixsort(int v[], int N)
{
    while(mx/exp>0)
    {
        countsort(v,N,exp);
        exp=exp*10;
    }
}

int main()
{
    int A,B,C;
    f>>N>>A>>B>>C;
    v[1]=B;
    mx=v[1];
    for(i=2;i<=N;i++)
        {v[i]=(1LL*v[i-1]*A+B)%C;
        mx=max(mx,v[i]);}
    radixsort(v,N);
    for(i=1;i<=N;i=i+10)
        g<<v[i]<<" ";
    f.close(); g.close();
    return 0;
}