Cod sursa(job #1322992)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 20 ianuarie 2015 16:32:30
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
 
int n;
int v[10000005], cate[10000005], u[10000005];

const int baza = (1 << 8) - 1;

void radix()
{
    long long pas = 0, i;
    while(pas < 31)
    {
    	memset (cate, 0, sizeof (cate));
    	
        for (i = 1; i <= n; i ++)
        	cate[(v[i] >> pas) & baza ] ++;
        for (i = 1; i <= baza; i ++)
        	cate[i] += cate[i - 1];
        
        for (i = n; i >= 1; i --)
        {
        	u[cate[(v[i] >> pas) & baza]] = v[i];
        	cate[(v[i] >> pas) & baza] --;
        }
        memcpy (v, u, sizeof (v));
        pas += 8;
    }
}
 
int main()
{
#ifdef INFOARENA
    freopen ("radixsort.in", "r", stdin);
    freopen ("radixsort.out", "w", stdout);
#endif    
    int a, b, c, i;
    
    cin >> n >> a >> b >> c;
    
    v[1] = b;
    
    for (i = 2; i <= n; i ++)
        v[i] = (1LL* a * v[i - 1] + b) % c;
    
    radix();
    
    for (i = 1; i <= n; i += 10)
    	cout << v[i] << ' ';
    return 0;
}