Cod sursa(job #2374939)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 7 martie 2019 21:21:49
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 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)

const int MAX_DIM = 10000000 + 16;
int numbers[MAX_DIM];
int N;

void sort_count(int *unsorted, int *sorted, 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 *temp = new int[N];
    for(unsigned i = 0; i < TOTAL_BYTES; ++i)
        if(i&1)
            sort_count(temp, numbers, i);
        else
            sort_count(numbers, temp, i);
}

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

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

    sort_radix();

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

    return 0;
}