Cod sursa(job #2551456)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 19 februarie 2020 20:51:18
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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 = 255;

    int i;

    int j;

    unsigned int mod = 0;

    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 += 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;

}