Cod sursa(job #2758831)

Utilizator LivcristiTerebes Liviu Livcristi Data 13 iunie 2021 11:40:45
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#define NUM 10000005

#define RADIX 0xFF
#define T_BYTES sizeof(int)

using namespace std;

int vec[NUM];
int n, a, b, c;

void radix(const int * source, int * dest, int byte)
{
    int count[256] = {0};

    for(int i = 0; i < n; ++i)
        count[(source[i] >> (byte * 8)) & RADIX]++;

    for(int i = 1; i < 256; ++i)
        count[i] += count[i-1];

    for(int i = n - 1; i >= 0; --i)
        dest[--count[(source[i] >> (byte * 8)) & RADIX]] = source[i];
}

void radixSort()
{
    int * new_array = new int[n];
    for(int i = 0; i < T_BYTES; ++i)
        if(i & 1)
            radix(new_array, vec, i);
        else
            radix(vec, new_array, i);
    delete[] new_array;
}

int main()
{
    ifstream f("radixsort.in");
    ofstream g("radixsort.out");
//    if(!f.is_open() || !g.is_open())
//        return 1;
    f >> n >> a >> b >> c;
    vec[0] = b;
    for(int i = 1; i < n; ++i)
    {
        vec[i] = (a * vec[i-1] + b) % c;
    }
    radixSort();
    for(int i = 0; i < n; i += 10)
        g << vec[i] << " ";
    f.close();
    g.close();
    return 0;
}