Cod sursa(job #2551471)

Utilizator Johnny07Savu Ioan-Daniel Johnny07 Data 19 februarie 2020 21:00:44
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 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;
    unsigned int poz;
    int shmt = 0;
	
    for (j = 1; j <= 4; j++)
	
    {
	
        for (i = 0; i <= 256; i++)
	
        {
	
            fr[i] = 0;
	
        }
	
        for (i = 1; i <= n; i++)
	
        {
            poz = v[i] >> shmt;
            poz = poz & 255;
            fr[poz + 1] ++ ;
	
        }
	
        for (i = 1; i <= 256; i++)
	
        {
	
            fr[i] += fr[i-1];
	
        }
	
        for (i = 1; i <= n; i++)
	
        {
            poz = v[i] >> shmt;
            poz = poz & 255;
            v_aux[fr[poz] + 1] = v[i];

            fr[poz] ++;
	
        }
	
        for (i = 1; i <= n; i++)
	
        {
	
            v[i] = v_aux[i];
	
        }
        shmt += 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;
	
}