Cod sursa(job #2855728)

Utilizator norryna07Alexandru Norina norryna07 Data 22 februarie 2022 20:39:04
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <iostream>
#define N 10000002
using namespace std;

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

int v[N], n;
int b[N];

int max_value(int a[], int n)
{
    int m=a[1];
    for (int i=2; i<=n; ++i) 
        if (a[i]>m) m=a[i];
    return m;
}

void countsort(int a[], int n, int exp)
{
    int f[10]={};
    for (int i=1; i<=n; ++i)
        f[(a[i]/exp)%10]++;
    
    ///determinam ultima pozitie a unui nr cu cifra x 
    for (int i=1; i<=9; i++)
        f[i]+=f[i-1];

    for (int i=n; i>=1; i--)
        b[f[(a[i]/exp)%10]]=a[i], f[(a[i]/exp)%10]--;
    for (int i=1; i<=n; ++i) a[i]=b[i];
}

void radixsort(int a[], int n)
{
    ///determinam maximul
    int m=max_value(a, n);

    for (int exp=1; exp<=m; exp*=10)
        countsort(a, n, exp);
}

int main()
{
    int a, b, c;
    fin>>n>>a>>b>>c;
    v[1]=b;
    for (int i=2; i<=n; ++i)
        v[i]=(1LL*a*v[i-1]+b)%c;
    radixsort(v, n);
    for (int i=1; i<=n; i+=10) fout<<v[i]<<' ';
    return 0;
    
}