Cod sursa(job #2596016)

Utilizator As932Stanciu Andreea As932 Data 8 aprilie 2020 23:54:30
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int nmax=10000005;

int n,a,b,c,v[nmax],cnt[nmax],out[nmax];

void read()
{
    fin>>n>>a>>b>>c;

    v[0]=b;
    for(int i=1;i<n;i++)
        v[i]=(a*v[i-1]+b)%c;
}

void countSort(int ex)
{
    memset(cnt,0,sizeof cnt);

    for(int i=0;i<n;i++)
        cnt[(v[i]/ex)%10]++;

    for(int i=1;i<=9;i++)
        cnt[i]+=cnt[i-1];

    for(int i=n-1;i>=0;i--)
    {
        out[cnt[(v[i]/ex)%10]-1]=v[i];
        cnt[(v[i]/ex)%10]--;
    }

    for(int i=0;i<n;i++)
        v[i]=out[i];
}

int maxim()
{
    int mx=v[0];
    for(int i=1;i<n;i++)
        mx=max(mx,v[i]);

    return mx;
}

void radixsort()
{
    int mx=maxim();

    for(int ex=1;mx/ex>0;ex*=10)
        countSort(ex);
}

void display()
{
    int poz=0;
    while(poz<n)
    {
        fout<<v[poz]<<" ";
        poz+=10;
    }
}

int main()
{
    read();
    radixsort();
    display();

    return 0;
}