Cod sursa(job #2542701)

Utilizator mihnea.anghelMihnea Anghel mihnea.anghel Data 10 februarie 2020 14:49:16
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#define f in
#define g out

using namespace std;
ifstream in ( "radixsort.in" );
ofstream out( "radixsort.out" );
const int baza = 256;
int n, a, b, c, i, j, maxi, cif, z, fr[baza];
int v[10000010], w[10000010];

int main() {
    f>>n>>a>>b>>c;
    v[1] = maxi = b;
    for ( i = 2; i <= n; i++ ){
        v[i] = (1LL*a*v[i-1]+b)%c;
        maxi = max ( maxi, v[i] );
    }
    while ( maxi ) {
        cif++;
        maxi /= baza;
    }
    z = 0;
    for ( c = 1; c <= cif; c++ ){
        for ( i = 1; i < baza; i++ )
            fr[i] = 0;
        for ( i = 1; i <= n; i++ )
            fr[ (v[i]>>z) & 255 ]++;
        for ( i = 1; i < baza; i++ )
            fr[i] += fr[i-1];
        for ( i = n; i; i-- )
            w[ fr[ (v[i]>>z) & 255 ]-- ] = v[i];
        for ( i = 1; i <= n; i++ )
            v[i] = w[i];
        z += 8;
    }
    
    for ( i = 1; i <= n; i += 10 )
        g<<v[i]<<" ";
    return 0;
}