Cod sursa(job #2571561)

Utilizator robx12lnLinca Robert robx12ln Data 5 martie 2020 08:14:58
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include<bits/stdc++.h>
using namespace std;

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

const int DIM = 1e7 + 5;

int N, A, B, C;
int arr[DIM], aux[DIM], cnt[300];

inline int f( int x, int p ){
    return ( (x>>p) & 255 );
}

int main(){
    fin >> N >> A >> B >> C;
    arr[1] = B;
    for( int i = 2; i <= N; i++ )
        arr[i] = (A * arr[i - 1] + B) % C;

    for( int p = 1; p <= 4; p++ ){
        for( int i = 1; i <= N; i++ )
            cnt[ f(arr[i], 8 * (p - 1)) ]++;
        for( int i = 1; i <= 255; i++ )
            cnt[i] += cnt[i - 1];
        for( int i = N; i >= 1; i-- )
            aux[ cnt[ f(arr[i], 8 * (p - 1)) ]-- ] = arr[i];
        memcpy( arr, aux, sizeof(aux) );
    }

    for( int i = 1; i <= N; i += 10 )
        fout << arr[i] << " ";
    return 0;
}