Cod sursa(job #2613746)

Utilizator vali_27Bojici Valentin vali_27 Data 10 mai 2020 16:45:46
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
#define NMAX 1000001
#define MOD 666013
using namespace std;


int n,baza = 32,mx;
vector <int> v,c;

void RadixSort()
{
    long long int p = 1;
    int cif[32] = {0};

    while(1LL*mx / p > 0)
    {
        memset(cif,0,sizeof(cif));

        for(int i=1;i<=n;++i)
            cif[ v[i]/p % baza ]++;

        for(int i=1;i<baza;++i)
            cif[i] += cif[i-1];

        for(int i=n;i>=1;--i)
        {
            c[ cif[ v[i]/p % baza ] ] = v[i];
            cif[v[i]/p % baza ]--;

        }
        for(int i=1;i<=n;++i)
            v[i] = c[i];

        p *= baza;
    }


}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    int A,B,C;
    scanf("%d %d %d %d",&n,&A,&B,&C);
    v.resize(n+1);
    c.resize(n+1);

    v[1] = B;
    mx = B;
    for(int i=2;i<=n;++i)
    {
        v[i] = (A * v[i-1] + B) % C;
        if(mx < v[i])mx = v[i];
    }


    RadixSort();

    for(int i=1;i<=n;i+=10)printf("%d ",v[i]);

//    sort(v.begin(),v.end());
//    printf("\n");
//    for(int i=1;i<=n;++i)printf("%d ",v[i]);
}