Cod sursa(job #2488434)

Utilizator maria15Maria Dinca maria15 Data 6 noiembrie 2019 21:58:13
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <bitset>

using namespace std;

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

int n, i, j, sol[10000001], v[10000001], nrcifre, maxim, x, nr, cif, a, b, c, divi;
int f[300], last[300];

int main(){
    fin>>n>>a>>b>>c;
    v[1] = maxim = b;
    for(i=2;i<=n;i++){
        v[i] = (a*1LL*v[i-1] + b)%c;
        if(v[i] > maxim)
            maxim = v[i];
    }
    while(maxim){
        nrcifre++;
        maxim /= 256;
    }
    for(j=1, divi = 0;j<=nrcifre;j++, divi += 8){
        for(i=0;i<256;i++)
            f[i] = 0;
        for(i=1;i<=n;i++){
            x = v[i];
            nr = 0;
            cif = ((x>>divi)&255);
            f[cif]++;
        }
        for(i=1;i<256;i++)
            f[i] += f[i-1], last[i] = f[i-1]+1;
        last[0] = 1;
        for(i=1;i<=n;i++){
            x = v[i];
            nr = 0;
            cif = ((x>>divi)&255);
            sol[last[cif]++] = v[i];
        }
        for(i=1;i<=n;i++)
            v[i] = sol[i];
    }
    for(i=1;i<=n;i+=10)
        fout<<v[i]<<" ";
    return 0;
}