Cod sursa(job #2574355)

Utilizator victorzarzuZarzu Victor victorzarzu Data 5 martie 2020 21:48:05
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int v[10000000];
int n, a, b, c;

#define TOTAL_BYTES sizeof(v[0])
#define RADIX 0xFF
#define RADIX_SIZE 8
#define get_byte(x) (x >> (8 * byte) & RADIX)

void Read()
{
    f>>n>>a>>b>>c;
}

void Solve()
{
    v[0] = b;
    for(int i = 1;i < n;++i)
        v[i] = ((1LL * a * v[i - 1]) % c + b) % c;
}

void CountSort(int A[], int B[], int byte)
{
    int counter[1 << RADIX_SIZE];
    int index[1 << RADIX_SIZE];

    memset(counter, 0, sizeof(counter));

    for(int i = 0;i < n;++i)
        counter[get_byte(A[i])]++;

    index[0] = 0;

    for(int i = 1;i < 1 << RADIX_SIZE;++i)
        index[i] = index[i - 1] + counter[i - 1];

    for(int i = 0;i < n;++i)
        B[index[get_byte(A[i])]++] = A[i];
}

void RadixSort()
{
    int *tmp = new int[n];
    for(int i = 0;i < TOTAL_BYTES;++i)
        if(i % 2 == 0)
            CountSort(v, tmp, i);
        else
            CountSort(tmp, v, i);
}

int main()
{
    Read();
    Solve();
    RadixSort();
    for(int i = 0;i < n;i += 10)
        g<<v[i]<<" ";
    return 0;
}