Cod sursa(job #2722839)

Utilizator alexbrinzaAlexandru Brinza alexbrinza Data 13 martie 2021 12:31:19
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
using namespace std;

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

vector < int > v;
int N, A, B, C;

void countsort(vector < int > &V, int b, int exponent)
{
    int size = V.size();
    vector < int > count(b, 0), new_sort(size, 0);

    for(int i = 0; i < size; ++i)
        ++count[(V[i] / exponent) % b];

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

    for(int i = size - 1; i >= 0; --i)
    {
        new_sort[count[(V[i] / exponent) % b] - 1] = V[i];
        --count[(V[i] / exponent) % b];
    }

    for(int i = 0; i < size; ++i)
        v[i] = new_sort[i];
    new_sort.clear();
}

void radixsort(vector < int > &V, int size, int b)
{
    int maxim = -1;

    for(int i = 0; i < size; ++i)
        maxim = max(V[i], maxim);
    
    int max_digits = int(log(maxim) / log(b)) + 1;
    int pow = 1;

    for(int i = 1; i <= max_digits; ++i)
    {
        countsort(V, b, pow);
        pow *= b;
    }
}

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

    v.push_back(B);
    for(int i = 1; i < N; ++i)
        v.push_back((A * v[i-1] + B) % C);

    radixsort(v, N, 256);

    for(int i = 0; i < N; i += 10)
        out << v[i] << " ";

    return 0;
}