Cod sursa(job #3128748)

Utilizator captn333Andreea Capitanu captn333 Data 10 mai 2023 20:03:28
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n;
int v[10000005];

void Citire();
void RadixSort();
void CountSort(int exp);
int GetMax();
void Afisare();

int main()
{
    Citire();
    RadixSort();
    Afisare();

    return 0;
}

void Citire()
{
    int A, B, C;
    fin >> n >> A >> B >> C;
    v[1] = B;
    for(int i = 2; i <= n; i++)
        v[i] = (A * v[i - 1] + B) % C;
}

void RadixSort()
{
    int maxi = GetMax();
    for(int exp = 1; maxi / exp > 0; exp *= 10)
        CountSort(exp);
}

void CountSort(int exp)
{
    int i;
    int v1[10000005], cnt[10] = {};
    for(i = 1; i <= n; i++)
        cnt[(v[i] / exp) % 10]++;
    for(i = 1; i < 10; i++)
        cnt[i] += cnt[i - 1];
    for(i = n; i >= 1; i--)
    {
        v1[cnt[(v[i] / exp) % 10]] = v[i];
        cnt[(v[i] / exp) % 10]--;
    }
    for(i = 1; i <= n; i++)
        v[i] = v1[i];
}

int GetMax()
{
    int maxi = v[1];
    for(int i = 2; i <= n; i++)
        maxi = max(maxi, v[i]);
    return maxi;
}

void Afisare()
{
    for(int i = 1; i <= n; i += 10)
        fout << v[i] << " ";
}