Cod sursa(job #3186833)

Utilizator StefantimStefan Timisescu Stefantim Data 25 decembrie 2023 20:39:09
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<bits/stdc++.h>
using namespace std;

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

const int NMAX = 1e7;
int v[NMAX + 5], n;
queue <int> q[15];

void sortare(int p)
{
    int k = 0;

    for(int i = 1; i <= n; ++i)
        q[v[i] / p % 10].push(v[i]);
    
    for(int i = 0; i <= 9; i++)
    {
        while(q[i].size())
        {
            v[++k] = q[i].front();
            q[i].pop();
        }
    }
}

void radix_sort()
{
    int maxim, nr, p;
    for(int i = 1; i <= n; ++i)
        maxim = max(maxim , v[i]);
    
    nr = 0, p = 1;
    while(maxim > 0)
    {
        maxim = maxim / 10;
        nr++;
    }
    for(int i = 1; i < nr; ++i)
        p = p * 10;
    for(int i = 1; i <= p ; i = i * 10)
    {
        sortare(i);
    }

}

int main()
{
    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;

    radix_sort();

    for(int i = 1; i <= n; ++i)
        fout << v[i] << " ";
    fout << "\n";
}