Cod sursa(job #1955643)

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

int main (){

    fin>>n>>a>>b>>c;
    v[1] = b;

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

        }
        // 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]>>(8*nr)) & 255  ]] = v[i];
            f[(v[i]>>(8*nr)) & 255]--;
        }

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

        nr++;
    }


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





    return 0;
}