Pagini recente » Cod sursa (job #1061759) | Cod sursa (job #1946901) | Cod sursa (job #649067) | Cod sursa (job #2306438) | Cod sursa (job #2945108)
///radixsort-LSD variant
/*#include <iostream>
#include <fstream>
#define Nmax 10000000
#define MaxBit 32
#define BitsPerStep 8
#define Mask ((1<<BitsPerStep)-1)
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int n,a,b,c;
int v1[Nmax], v2[Nmax], ind[Mask+1], fr[Mask+1];
void radixsort(int v[], int aux[], int bit){
if (bit==MaxBit)
return;
for (int i=0;i<=Mask;i++)
fr[i]=0;
for (int i=0;i<n;i++)
fr[(v[i]>>bit)%Mask]++;
ind[0]=0;
for (int i=1;i<=Mask;i++)
ind[i]=ind[i-1]+fr[i-1];
for (int i=0;i<n;i++)
aux[ind[(v[i]>>bit)%Mask]++]=v[i];
radixsort(aux, v, bit+BitsPerStep);
}
int main()
{
fin>>n>>a>>b>>c;
v1[0]=b;
for (int i=1;i<n;i++){
v1[i]=((long long)a*v1[i-1]+b)%c;
}
radixsort(v1, v2, 0);
for (int i=0;i<n;i+=10)
fout<<v1[i]<<' ';
return 0;
}*/
#include <iostream>
#include <fstream>
#define MAX_N 10000000
#define MAX_BITS 32
#define BITS_PER_STEP 8
#define MASK ((1 << BITS_PER_STEP) - 1)
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
int v1[MAX_N], v2[MAX_N];
int freq[MASK+1], ind[MASK+1];
int n,a,b,c;
void sort(int v[], int aux[], int bits) {
if (bits == MAX_BITS)
return;
for (int i=0;i<=MASK;i++)
freq[i]=0;
int i;
for (i = 0; i < n; ++i)
++freq[v[i] >> bits & MASK];
ind[0] = 0;
for (i = 1; i <= MASK; ++i)
ind[i] = ind[i - 1] + freq[i - 1];
for (i = 0; i < n; ++i)
aux[ind[v[i] >> bits & MASK]++] = v[i];
sort(aux, v, bits + BITS_PER_STEP);
}
int main() {
fin>>n>>a>>b>>c;
v1[0]=b;
for (int i = 1; i < n; ++i)
v1[i]=((long long)v1[i-1]*a+b)%c;
sort(v1, v2, 0);
for (int i = 0; i < n; i+=10)
fout<<v1[i]<<' ';
return 0;
}