Cod sursa(job #2001413)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 16 iulie 2017 17:06:03
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

const int NMAX = 10000005;

int v[NMAX],aux[NMAX],N,A,B,C;

void read()
{

    in>>N>>A>>B>>C;
    v[1] = B;
    for(int i = 2 ; i <= N ; ++i)
        v[i] = (A*v[i-1] + B)%C;
}

void countSort(int digit)
{

    int f[11];
    for(int i = 0 ; i <= 9 ; ++i)
        f[i] = 0;
    for(int i = 1 ; i <= N ; ++i)
        f[(v[i]/digit)%10] ++;
    for(int i = 1 ; i <= 9 ; ++i)
        f[i] += f[i-1];
    for(int i = N ; i > 0 ; --i){
        aux[f[(v[i]/digit)%10]] = v[i];
        f[(v[i]/digit)%10] --;
    }
    for(int i = 1 ; i <= N ; ++i)
        v[i] = aux[i];
}

void radixSort()
{

    int maxim = -1;
    for(int i = 1 ; i <= N ; ++i)
        maxim = max(maxim,v[i]);
    for(int p = 1 ; maxim / p > 0 ; p *= 10 )
        countSort(p);
}

void afis()
{

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

int main()
{

    read();
    radixSort();
    afis();
    return 0;
}