Cod sursa(job #1955342)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 5 aprilie 2017 21:59:21
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <iostream>
using namespace std;
long long n,a,b,c,i,maxim,nr,ok;
int v[10000001],f[11],w[10000001];
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int main (){

    fin>>n>>a>>b>>c;
    v[1] = b;
    maxim = 1;
    for (i=2;i<=n;i++){
        v[i] = (1LL*a*v[i-1]+b)%c;
        //if (v[i] > maxim)
          //  maxim *= 1LL * 256;
    }
    nr = 256;
    while (n >= ok){
        // initializam vectorul de frecventa
        for (i=0;i<=255;i++)
            f[i] = 0;
        for (i=1;i<=n;i++){
            f[(v[i]/(nr/256) )%256]++;
            if (256 >= (v[i]/(nr/256) ))
                ok++;
        }
        // facem sume partiale
        for (i=1;i<=255;i++)
            f[i] += f[i-1];

        for (i=n;i>=1;i--){
            //f[(v[i]/nr)%10] - ultima pozitie pe care se afla (v[i]/nr)%10
            w[f[(v[i]/(nr/256) )%256]] = v[i];
            f[(v[i]/(nr/256) )%256]--;
        }

        for (i=1;i<=n;i++)
            v[i] = w[i];

        nr *= 256;
    }


    for (i=1;i<=n;i+=10)
        fout<<v[i]<<" ";





    return 0;
}