Cod sursa(job #2851045)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 17 februarie 2022 23:08:20
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 1e7 + 5;
int N, a, b, c;
int v[Nmax];
const int BYTES = sizeof(v[0]);
const int BLOCK_SIZE = 0xFF;
const int BITB_SIZE = 8;

inline int get_byte(int x, int byte)
{
    return (x >> (byte * 8) & BLOCK_SIZE);
}

void count_sort(int *A, int *B, int byte)
{
    int counter[(1 << BITB_SIZE)];
    int index[(1 << BITB_SIZE)];

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

    for(int i = 0; i < N; ++i)
    {
        counter[get_byte(A[i], byte)]++;
    }

    index[0] = 0;

    for(int i = 1; i < (1 << BITB_SIZE); ++i)
    {
        index[i] = index[i - 1] + counter[i - 1];
    }
    int byte_curr;
    for(int i = 0; i < N; ++i)
    {
        byte_curr = get_byte(A[i], byte);
        B[index[byte_curr]++] = A[i];
    }
}

void radix_sort()
{
    int *aux = new int [N + 1];
    /*for(int i = 0; i < N; ++i)
    {
        cout << aux[i] << " ";
    }*/
    /*
    de ce numai elementele de la aux[2] incolo sunt 0?
    */
    for(int i = 0; i < BYTES; ++i)
    {
        if(i % 2 == 0)
        {
            count_sort(v, aux, i);
        }
        else
        {
            count_sort(aux, v, i);
        }
    }
}

int main()
{
    in >> N >> a >> b >> c;
    v[0] = b;
    for(int i = 1; i < N; ++i)
    {
        v[i] = (1LL * a * v[i - 1] + b) % c;
    }
    radix_sort();
    for(int i = 0; i < N; i += 10)
    {
        out << v[i] << " ";
    }
    return 0;
}