Cod sursa(job #2807699)

Utilizator puica2018Puica Andrei puica2018 Data 24 noiembrie 2021 09:31:44
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,x,y,z;
int a[1000005],t[1000005];
int cnt[256];

void solve()
{
    for(int b=0; b<4; b++)
    {
        fill(t+1,t+n+1,0);
        fill(cnt,cnt+256,0);
        int i;
        for(i=1; i<=n; i++)
            cnt[(a[i]>>(8*b))&255]++;
        for(i=1; i<=256; i++)
            cnt[i]+=cnt[i-1];
        for(i=256; i>=1; i--)
            cnt[i]=cnt[i-1];
        cnt[0]=0;
        for(i=1; i<=n; i++)
            t[++cnt[(a[i]>>(8*b))&255]]=a[i];
        for(i=1; i<=n; i++)
            a[i]=t[i];
    }
}

int main()
{
    fin>>n>>x>>y>>z;
    int i;
    a[1]=y;
    for(i=2; i<=n; i++)
        a[i]=(1LL*a[i-1]*x%z+y)%z;
    solve();
    for(i=1; i<=n; i+=10)
        fout<<a[i]<<" ";
    fout<<"\n";
    return 0;
}