Cod sursa(job #2361696)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 2 martie 2019 18:00:51
Problema Radix Sort Scor 30
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 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)
        aux[++index[get_byte(V[i])]] = V[i];

    for(int i = 1; i <= lg; ++i)
        V[i] = aux[i];
}

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

int main()
{
    freopen("radixsort.out", "w", stdout);
    long long 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] = (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] << ' ';
    return 0;
}