Cod sursa(job #1974648)

Utilizator mihailarminia1234Arminia Mihail mihailarminia1234 Data 28 aprilie 2017 12:35:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

#define MAXN 10000001

using namespace std;

int N, A, B, C, v[MAXN], a[10][MAXN], p = 1, loc;

void Construire()
{
        v[1] = B;
        for(int i = 2; i <= N; ++i) v[i] = (A * v[i-1] + B) % C;
}

void RadixSort()
{
        for(int i = 1; i <= 9; ++i)
        {
                for(int j = 0; j <= 9 ; ++j) a[j][0] = 0;

                for(int j = 1; j <= N; ++j)
                {
                        int x = v[j];
                        int linie = x/p%10;
                        ++a[linie][0];
                        a[linie][a[linie][0]] = x;
                }
                loc = 0;
                for(int k = 0; k <= 9; ++k)
                {
                        for(int j = 1; j <= a[k][0]; ++j)
                        {
                                ++loc;
                                v[loc] = a[k][j];
                        }
                }
                p *= 10;
        }
}

void Afisare()
{
        for(int i = 1; i <= N; i += 10) printf("%d ", v[i]);
}

int main()
{
        freopen("radixsort.in", "r", stdin);
        freopen("radixsort.out", "w", stdout);
        scanf("%d %d %d %d", &N, &A, &B, &C);
        Construire();
        RadixSort();
        Afisare();
        return 0;
}