Cod sursa(job #2225881)

Utilizator CristianSoareSoare Cristian Costantin CristianSoare Data 28 iulie 2018 15:37:36
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
using namespace std;

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

long long v[100000];

void out(long long v[], long long n){
    long long i;
    for (i = 0;i < n;i += 10)
        fout << v[i] << " ";
}

void radixSort(long long v[], long long n, long long maxi){
    long long i, bucket[100000], e = 1, nr[100000];
    while (maxi/e > 0){
        for(i = 0; i < 10; i++)
            nr[i] = 0;
        for (i = 0;i < n;i++)
            nr[(v[i]/e)%10]++;
        for (i = 1;i < n;i++)
            nr[i] += nr[i-1];
        for (i = n-1;i >= 0;i--){
            bucket[nr[(v[i]/e)%10]-1] = v[i];
            nr[(v[i]/e)%10]--;
        }
        for (i = 0;i < n;i++)
            v[i] = bucket[i];
        e *= 10;
    }
}

int main(){
    long long n, maxi = 0, a, b, c, i;
    fin >> n >> a >> b >> c;
    v[0] = b;
    for (i = 1;i < n;i++){
        v[i] = (a*v[i-1]+b)%c;
        if (v[i] > maxi)
            maxi = v[i];
    }
    radixSort(v, n, maxi);
    out(v, n);
    fin.close();
    fout.close();
    return 0;
}