Cod sursa(job #2509351)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 decembrie 2019 10:12:16
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#include <vector>
#include <cstring>

#define NMAX 10000005

using namespace std;

int v[NMAX], maxx, n, fr[257], aux[NMAX];

inline int get_byte(const int& x, const int& byte)
{
    return ((x >> (byte * 8)) & ((1 << 8) - 1));
}

void countingSort ( int v[], int aux[], int byte ) {
    memset ( fr, 0, sizeof ( fr ) );

    for ( int i = 1; i <= n; ++i )
        fr[get_byte(v[i], byte)]++;

    for ( int i = 1; i <= 256; ++i )
        fr[i] += fr[i - 1];

    for ( int i = n; i >= 1; --i ) {
        aux[fr[get_byte(v[i], byte)]] = v[i];
        fr[get_byte(v[i], byte)]--;
    }
}

void sortR() {
    for (int byte = 0; byte < 4; ++byte)
        if ( byte % 2 == 0 )
            countingSort ( v, aux, byte);
        else countingSort ( aux, v, byte);
}

int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

    int a, b, c;
    scanf("%d%d%d%d", &n, &a, &b, &c);

    v[1] = b;
    for(int i = 2; i <= n; ++i)
        v[i] = (a * v[i - 1] + b) % c;


    sortR();

    for ( int i = 1; i <= n; i += 10)
        printf("%d ", v[i]);
    return 0;
}