Cod sursa(job #3186862)

Utilizator StefantimStefan Timisescu Stefantim Data 26 decembrie 2023 02:17:00
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include<bits/stdc++.h>
using namespace std;

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

const int NMAX = 1e7;
int v[NMAX + 5], w[NMAX + 5], n;
int c[15], d[15];
void sortare(int p)
{
    for(int i = 0; i < 10; ++i)
        c[i] = 0;
    for(int i = 1; i <= n; ++i)
        c[v[i] / p % 10]++;
    d[0] = 1;
    for(int i = 1; i < 10; ++i)
        d[i] = d[i - 1] + c[i - 1];
    
    for(int i = 1; i <= n; ++i)
    {   
        w[d[v[i] / p % 10]] = v[i];
        d[v[i] / p % 10]++;
    }

    for(int i = 1; i <= n; ++i)
        v[i] = w[i];
}

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

}

int main()
{
    int a, b, c;
    fin >> n >> a >> b >> c;
    v[1] = b;
    for(long long i = 2; i <= n; ++i)
        v[i] = (1LL * a * v[i-1] + b) % c;

    radix_sort();

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