Cod sursa(job #2230100)

Utilizator danielsociuSociu Daniel danielsociu Data 9 august 2018 08:05:43
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
std::ifstream cin("radixsort.in");
std::ofstream cout("radixsort.out");
#define maxn 10000001
int N,A,B,C,v[maxn],output[maxn],counter[10];


int countSort(int exp){
    for(int i=0;i<10;i++)
        counter[i]=0;
    for(int i=1;i<=N;i++)
        counter[(v[i]/exp)%10]++; //numar de cifre
    for(int i=1;i<10;i++)
        counter[i]+=counter[i-1];//pozitii in output(v[i])
    for(int i=N;i>0;i--){
        output[counter[(v[i]/exp)%10]]=v[i];
        counter[(v[i]/exp)%10]--;//atribuire solutie partiala(bazata pe exp)
    }
    for(int i=1;i<=N;i++)
        v[i]=output[i];
}

int main()
{
    int maxim=1>>31;
    cin>>N>>A>>B>>C;
    v[1]=B;
    for(int i=2;i<=N;i++)
        v[i]=(A*v[i-1]+B)%C;
    for(int i=1;i<=N;i++)
        if(v[i]>maxim)
            maxim=v[i];
    for(int exp=1;maxim/exp>0;exp*=10)
        countSort(exp);
    for(int i=1;i<=N;i+=10)
        cout<<v[i]<<" ";
}