Pagini recente » Cod sursa (job #261699) | Cod sursa (job #1909939) | Cod sursa (job #2238122) | Cod sursa (job #2750814) | Cod sursa (job #2681026)
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000000
#define MAXBITS 32
#define DIGIT_SIZE 4
#define BUCKETS (1<<DIGIT_SIZE)
#define MASK ((1<<DIGIT_SIZE)-1)
vector <int> bucket[BUCKETS];
int v[MAXN], v_aux[MAXN], freq[BUCKETS], ind[BUCKETS];
int find_bucket(int x, int bits){
return (x>>bits)&MASK;
}
void radsort(int v[], int v_aux[], int n, int bits){
if (bits==MAXBITS) return;
int i;
for (i=0; i<BUCKETS; i++) freq[i]=0;
for (i=0; i<n; i++){
freq[find_bucket(v[i], bits)]++;
}
ind[0]=0;
for (i=1; i<BUCKETS; i++) ind[i]=ind[i-1]+freq[i-1];
for (i=0; i<n; i++){
v_aux[ind[find_bucket(v[i], bits)]++]=v[i];
}
radsort(v_aux, v, n, bits+DIGIT_SIZE);
}
int main()
{
FILE *fin=fopen("radixsort.in", "r");
FILE *fout=fopen("radixsort.out", "w");
int n, a, b, c;
fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
const int A=a, B=b, C=c, skip=10;
v[0]=B;
int i;
for (i=1; i<n; i++){
v[i]=(long long int)(A*v[i-1]+B)%C;
}
radsort(v, v_aux, n, 0);
for (i=0; i<n; i+=skip) fprintf(fout, "%d ", v[i]);
return 0;
}