Cod sursa(job #2388963)

Utilizator AlexTudorAlex Brinza AlexTudor Data 26 martie 2019 18:37:47
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX=10000005;

int v[NMAX];

int N,A,B,C;
int val;
int maxim;
int range=10;

void read()
{
    fin>>N>>A>>B>>C;

    v[1]=B;

    maxim=B;

    for(int i=2;i<=N;++i)
    {
        val=(1LL*A*v[i-1] + B)%C;

        //fin>>val;

        if(val>maxim) maxim=val;

        v[i]=val;
    }

}

void count(int place)
{
    int i;
    int frecv[10]={0};
    int out[N];

    for(int i=1;i<=N;++i)
        frecv[ (v[i]/place) % range ]++;

    for(int i=1;i<range;++i)
        frecv[i]+=frecv[i-1];

    for(int i=N;i>=1;--i)
    {
        out[ frecv[ (v[i]/place) % range] ] = v[i];
        frecv[ (v[i]/place) % range]--;
    }

    for(int i=1;i<=N;++i)
        v[i]=out[i];
}

void radix()
{
    int p=1;

    while(maxim)
    {
        count(p);

        maxim/=10;
        p*=10;
    }
}

int main()
{
    read();
    radix();

    int x=1;

    //for(int i=1;i<=N;++i) fout<<v[i]<<" ";

    while(x<=N)
    {
        fout<<v[x]<<" ";
        x+=10;
    }
    return 0;
}