Cod sursa(job #2679752)

Utilizator PopescuAndreiAlexandruPopescu Andrei Alexandru PopescuAndreiAlexandru Data 1 decembrie 2020 13:53:33
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 10000005;

int n,a,b,c,v[DIM],Sol[DIM],m,p,Hash[11];

void Read()
{
    fin>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
            v[i]=(a*v[i-1]+b)%c;
}

void GetMax()
{
    for(int i=1;i<=n;i++)
            m=max(m,v[i]);
}

void CountSort(int power)
{
    for(int i=0;i<10;i++)
        Hash[i]=0;
    for(int i=1;i<=n;i++)
        Hash[(v[i]/power)%10]++;
    for(int i=1;i<10;i++)
        Hash[i]+=Hash[i-1];
    for(int i=n;i>=1;i--)
        {
            Sol[Hash[(v[i]/power)%10]]=v[i];
            Hash[(v[i]/power)%10]--;
        }
    for(int i=1;i<=n;i++)
            v[i]=Sol[i];
}

void RadixSort()
{
    for(int i=1;i<=m;i*=10)
        CountSort(i);
}

void Print()
{
    for(int i=1;i<=n;i+=10)
            fout<<v[i]<<" ";
    fout<<'\n';
}

int main()
{
    Read();
    GetMax();
    RadixSort();
    Print();
}