Cod sursa(job #2361748)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 2 martie 2019 18:17:36
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

#define RADIX 0xFF
#define get_byte(x) ((x >> (byte * 8)) & RADIX)
#define NMAX 10000005
using namespace std;

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

int v[NMAX], aux[NMAX];

void countSort(int V[], int B[], int lg, int byte){
    int xCount[256];
    int index[256];

    memset(xCount, 0, sizeof(xCount));

    for(int i = 1; i <= lg; ++i)
        xCount[get_byte(V[i])]++;

    index[0] = 0;

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

    for(int i = 1; i <= lg; ++i)
        B[++index[get_byte(V[i])]] = V[i];
}

void radixSort(int vec[], int lg, int maxx){
    int nrBytes = sizeof(vec[1]);
    for(int i = 0; i < nrBytes; ++i)
        if(i % 2 == 0)
            countSort(vec, aux, lg, i);
        else countSort(aux, vec, lg, i);
}

int main()
{
    int n, a, b, c;
    fin >> n >> a >> b >> c;

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

    radixSort(v, n, maxx);

    for(int i = 1; i <= n; i += 10)
        fout << v[i] << ' ';
    fout << '\n';
    return 0;
}