Mai intai trebuie sa te autentifici.

Cod sursa(job #2521869)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 11 ianuarie 2020 17:13:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 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 a[] , int output[])
{
    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];
}

void Print(int a[])
{
    for(int i = 1 ; i <= n ; i += 10)
        g << a[i] << ' ';
}

void RadixSort(int maxx)
{
    int exp;

    bool ult = 0;

    for(exp = 1 ; maxx / exp > 0 ; exp *= 10 , ult = !ult)
    {
        if(ult == 0)
            CountSort(exp , a , output);
        else CountSort(exp , output , a);
    }

    if(!ult == 0)
        Print(output);
    else Print(a);
}

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);

    return 0;
}