Cod sursa(job #2215696)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 23 iunie 2018 11:34:24
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>

using namespace std;

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

const int N=10000000;
const int MOD=(1<<10);

int n;
int a,b,c;
int v[N+5],aux[N+5];
int ap[MOD+5];

int main()
{
    fin>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
        v[i]=((long long)v[i-1]*a+b)%c;
    int p=1;
    while(1)
    {
        for(int i=0;i<MOD;i++)
            ap[i]=0;
        bool gasit=0;
        for(int i=1;i<=n;i++)
        {
            int val=v[i]/p;
            if(val)
                gasit=1;
            ap[val%MOD]++;
        }
        if(gasit==0)
            break;
        for(int i=1;i<MOD;i++)
            ap[i]+=ap[i-1];
        for(int i=n;i>=1;i--)
            aux[ap[v[i]/p%MOD]]=v[i],ap[v[i]/p%MOD]--;
        for(int i=1;i<=n;i++)
            v[i]=aux[i];
        p*=MOD;
    }
    for(int i=1;i<=n;i+=10)
        fout<<v[i]<<" ";
    fout<<"\n";
    return 0;
}