Cod sursa(job #2682478)

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

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n;
long long a[10000001];
long long 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--)
    {
        int x = a[i] / exp;
        x %= 10;
        b[c[x]] = a[i];
        c[x]--;
    }
    for (int i = 1; i <= n; i++)
        a[i] = b[i];
}

void radix()
{
    long long 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] = (1LL *A * a[i - 1] + 1LL*B) % C*1LL;
    radix();
    for (int i = 1; i <= n; i+=10)
        fout << a[i] << " ";
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}