Cod sursa(job #3224251)

Utilizator Simon2712Simon Slanina Simon2712 Data 14 aprilie 2024 23:35:17
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
#define ll long long
const int N=1e8+1;
int v[N],vc[N],vrez[N];
int main()
{
    int n,a,b,c,maxi,i;
    ll exp;
    fin>>n>>a>>b>>c;
    v[1]=b;
    maxi=v[1];
    for(i=2;i<=n;i++){
        v[i]=(1LL*a*v[i-1]+b)%c;
        maxi=max(maxi,v[i]);
    }
    exp=1;
    while(exp<maxi)
    {
        for(i=1;i<=n;i++)
            vc[(v[i]/exp)%10]++;
        for(i=1;i<=9;i++)
            vc[i]+=vc[i-1];
        for(i=n;i>0;i--)
        {
            vrez[vc[(v[i]/exp)%10]]=v[i];
            vc[(v[i]/exp)%10]--;
        }
         for(i=1;i<=n;i++)
            v[i]=vrez[i];
        for(i=0;i<=9;i++)
            vc[i]=0;
        exp*=10;
    }
    for(i=1;i<=n;i+=10)
        fout<<v[i]<<" ";
    return 0;
}