Cod sursa(job #2375012)

Utilizator AlexiaPaunescu100Alexia Paunescu AlexiaPaunescu100 Data 7 martie 2019 21:47:19
Problema Radix Sort Scor 60
Compilator cpp-64 Status done
Runda testare_olimpiada Marime 1.42 kb
#include <fstream>
#include <cstring>
using namespace std;

#define FILE_NAME "radixsort"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");

#define RADIX_MASK 0xFF
#define RADIX_WORD_SIZE 8
#define TOTAL_BYTES sizeof(int)
#define GET_BYTE(x, b) ((x>>(RADIX_WORD_SIZE * b))&RADIX_MASK)

void sort_count(int *unsorted, int *sorted, int N, int byte)
{
    int index[1<<RADIX_WORD_SIZE];
    int freq[1<<RADIX_WORD_SIZE];

    memset(freq, 0, sizeof(freq));

    for(int i = 0; i < N; ++i)
        ++freq[ GET_BYTE(unsorted[i], byte) ];

    index[0] = 0;

    for(int i = 1; i < (1 << RADIX_WORD_SIZE); ++i)
        index[i] = index[i-1] + freq[i-1];

    for(int i = 0; i < N; ++i)
        sorted[ index[ GET_BYTE(unsorted[i], byte) ]++ ] = unsorted[i];
    /// dont forget that ++ !!
}

void sort_radix(int *numbers, int N)
{
    int *temp = (int*) malloc(N * sizeof(int));
    for(unsigned i = 0; i < TOTAL_BYTES; ++i)
        if(i&1)
            sort_count(temp, numbers, N, i);
        else
            sort_count(numbers, temp, N, i);
}

int main()
{
    int N, A, B, C;
    in >> N >> A >> B >> C;

    int *numbers = (int*) malloc(N * sizeof(int));
    numbers[0] = B % C;
    for(int i = 1; i < N; ++i)
        numbers[i] = (1LL * A * numbers[i-1] % C + B) % C;

    sort_radix(numbers, N);

    for(int i = 0; i < N; i += 10)
        out << numbers[i] << ' ';

    return 0;
}