Cod sursa(job #2551450)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 19 februarie 2020 20:41:14
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>

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

unsigned int v[10000005];
unsigned int v_aux[10000005];
int n;
unsigned long long a, b, c;
int fr[300];

void radixSort()
{
    unsigned int base = 256;
    int i;
    int j;
    unsigned int mod = 1;
    for (j = 1; j <= 4; j++)
    {
        for (i = 0; i <= 256; i++)
        {
            fr[i] = 0;
        }
        for (i = 1; i <= n; i++)
        {
            fr[(v[i]/mod)%base + 1] ++ ;
        }
        for (i = 1; i <= 256; i++)
        {
            fr[i] += fr[i-1];
        }
        for (i = 1; i <= n; i++)
        {
            v_aux[fr[(v[i]/mod)%base] + 1] = v[i];
            fr[(v[i]/mod)%base] ++;
        }
        for (i = 1; i <= n; i++)
        {
            v[i] = v_aux[i];
        }
        mod = mod << 8;
    }

}

int main()
{
    int i;
    f >> n >> a >> b >> c;
    v[1] = b;
    unsigned long long aux;
    for (i = 2; i <= n; i++)
    {
        aux = v[i-1] * a + b;
        aux %= c;
        v[i] = aux;
    }
    radixSort();
    for (i = 1; i <= n; i += 10)
    {
        g << v[i] << " ";
    }

    return 0;
}