Cod sursa(job #2682476)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 8 decembrie 2020 18:59:12
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n;
int a[10000001];
int b[10000001];
void countsort(int exp)
{
    int c[10] = { 0 };
    for (int i = 1; i <= n; i++)
        c[(a[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        c[i] += c[i - 1];
    for (int i = n; i >= 1; i--)
    {
        b[c[(a[i] / exp) % 10]] = a[i];
        c[(a[i] / exp) % 10]--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = b[i];
}

void radix()
{
    int maxx = 0;
    for (int i = 1; i <= n; i++)
        maxx = max(a[i], maxx);
    for (int exp = 1; maxx / exp > 0; exp *= 10)
        countsort(exp);
}


int main()
{
    int A, B, C;
    fin >> n >> A >> B >> C;
    a[1] = B;
    for (int i = 2; i <= n; i++) 
        a[i] = (A * a[i - 1] + B) % C;
    radix();
    for (int i = 1; i <= n; i++) {
        if(i % 10 == 1)
        fout << a[i] << " ";
    }
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}