Pagini recente » Cod sursa (job #240575) | Cod sursa (job #2929172) | Cod sursa (job #2091117) | Cod sursa (job #476382) | Cod sursa (job #3175777)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
int N, a, b, c, cur, l = 0, l2 = 0;
#define MAX_N 10000001
#define MAX_BITS 31
#define BITS_PER_STEP 8
const int BASE = (1 << BITS_PER_STEP);
const int MASK = BASE - 1;
int v[MAX_N];
int v2[MAX_N];
int v_aux[MAX_N];
int freq[BASE];
int ind[BASE];
//vector <long long> v;
//vector <long long> v2;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
int Sort( int v[], int aux[], int n, int bits )
{
if( bits >= MAX_BITS )
return 0;
int i;
for( i = 0; i < n; ++i )
freq[i] = 0;
//memset(freq, 0, sizeof(freq));
for( i = 0; i < n; ++i )
{
++freq[ v[i] >> bits & MASK ];
}
ind[0] = 0;
for( i = 1; i < BASE; ++i )
{
ind[i] = ind[i-1] + freq[i - 1];
}
for( i = 0; i < n; ++i )
{
ind[ v[i] >> bits & MASK ]++;
aux[ ind[ v[i] >> bits & MASK ] ] = v[i];
}
Sort( v, aux, n, bits + BITS_PER_STEP );
return 0;
}
int main()
{
ios_base::sync_with_stdio(false);
f.tie(NULL); g.tie(NULL);
f >> N >> a >> b >> c;
v[0] = b;
cur = b;
for( int i = 1; i < N; ++i )
{
cur = (a * cur + b) % c;
v[i] = cur;
//if( (i - 1) % 10 == 0 )
//{
// ++l;
//}
}
Sort( v, v_aux, N, 0 );
int st = 0;
while( st < N )
{
g << v[st] << " ";
if( st % 10 == 0 )
v2[l2] = v[st], ++l2;
++st;
}
st = 0;
while( st < l2 )
{
//g << v2[st] << " ";
++st;
}
return 0;
}