Cod sursa(job #2521812)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 11 ianuarie 2020 15:56:14
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 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)
{
    memset(countt , 0 , sizeof(countt));
    memset(output , 0 , sizeof(output));

    int i;

    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];
        --countt[ a[i] / exp % 10 ];
    }

    memcpy(a , output , sizeof(output));
}

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] = (A * a[i - 1] % C + B) % C;
        maxx = max(maxx , a[i]);
    }

    RadixSort(maxx);

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

    return 0;
}