Cod sursa(job #2481767)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 27 octombrie 2019 13:24:29
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 10000005;
const int RADIX = 0xFF;
const int SIZE = 1 << 8;
int V[NMAX], N, A, B, C;

int getByte(int x, int b)
{
    return ((x >> (b * 8)) & RADIX);
}

void countSort(int A[], int B[], int b)
{
    int counter[SIZE];
    int index[SIZE];

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

    for(int i = 0; i < N; ++i)
        ++counter[getByte(A[i], b)];

    index[0] = 0;

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

    for(int i = 0; i < N; ++i)
        B[index[getByte(A[i], b)]++] = A[i];
}

void radixSort()
{
    int *temp = new int[N];
    for(int i = 0; i < sizeof(V[0]); ++i)
        if(i & 1)
            countSort(temp, V, i);
        else
            countSort(V, temp, i);
}

void generateArr()
{
    fin >> N >> A >> B >> C;

    V[0] = B % C;
    for(int i = 1; i < N; ++i) {
        V[i] = (1LL * A * V[i-1] % C + B) % C;
    }
}

int main()
{
    generateArr();

    radixSort();

    for(int i = 0; i < N; i += 10)
        fout << V[i] << " ";
    fout << "\n";
}