Cod sursa(job #2521819)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 11 ianuarie 2020 16:03:27
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define N 10000005

using namespace std;

ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

int n , A , B , C;
int a[N] , countt[10] , output[N];

void CountSort(int exp)
{
    int i;

    for(i = 0 ; i < 10 ; i++)
        countt[i] = 0;

    for(i = 1 ; i <= n ; i++)
        ++countt[ a[i] / exp % 10 ];

    for(i = 0 ; i < 10 ; i++)
        countt[i] += countt[i - 1];

    for(i = n ; i >= 1 ; i--)
        output[ countt[ a[i] / exp % 10 ]-- ] = a[i];

    for(i = 1 ; i <= n ; i++)
        a[i] = output[i];
}

void RadixSort(int maxx)
{
    int exp;

    for(exp = 1 ; maxx / exp > 0 ; exp *= 10)
        CountSort(exp);
}

int main()
{
    ios_base::sync_with_stdio(false) , cin.tie(0);

    int i , maxx = 0;

    f >> n >> A >> B >> C;

    a[1] = B;
    maxx = B;

    for(i = 2 ; i <= n ; i++)
    {
        a[i] = (1ll * A * a[i - 1] + B) % C;
        maxx = max(maxx , a[i]);
    }

    RadixSort(maxx);

    for(i = 1 ; i <= n ; i += 10)
        g << a[i] << ' ';

    return 0;
}