Pagini recente » Cod sursa (job #921526) | Cod sursa (job #2081886) | Cod sursa (job #3247017) | Cod sursa (job #1096781) | Cod sursa (job #2532120)
#include <bits/stdc++.h>
using namespace std;
ofstream g("radixsort.out");
int n,a,b,c;
int p = 31999;
char buffer[32010];
#define MAX_N 10000001
#define RADIX 0xFF
#define RADIX_SIZE 8
int numbers[MAX_N];
#define TOTAL_BYTES sizeof(numbers[0])
#define get_byte(x) ((x >> (byte * 8)) & RADIX)
void inc()
{
++p;
if(p == 32000)
{
fread(buffer,1,32000,stdin);
p = 0;
}
}
void read(int &x)
{
x = 0;
while(buffer[p] < '0' || buffer[p] > '9')
inc();
while(buffer[p] >= '0' && buffer[p] <= '9')
{
x = x * 10 + buffer[p] - '0';
inc();
}
}
void Read()
{
freopen("radixsort.in","r",stdin);
read(n);
read(a);
read(b);
read(c);
}
void Solve()
{
int last = b,current;
numbers[0] = b % c;
for(int i = 1; i < n; i++)
numbers[i] = (1LL * a * numbers[i-1] % c + b) % c;
}
void countSort(int A[],int B[],int byte)
{
int counter[1 << RADIX_SIZE];
int index[1 << RADIX_SIZE];
memset(counter, 0 , sizeof(counter));
for(int i = 0;i < n;++i)
++counter[get_byte(A[i])];
index[0] = 0;
for(int i = 1;i < 1 << RADIX_SIZE;++i)
index[i] = index[i - 1] + counter[i - 1];
for(int i = 0;i < n;++i)
B[index[get_byte(A[i])]++] = A[i];
}
void RadixSort()
{
int *temp = new int[n];
for(int i = 0; i < TOTAL_BYTES;++i)
if(i % 2 == 0)
countSort(numbers, temp, i);
else countSort(temp, numbers, i);
}
void Print()
{
for(int i = 0; i < n - 1;i += 10)
g<<numbers[i]<<" ";
g.close();
}
int main()
{
Read();
Solve();
RadixSort();;
Print();
return 0;
}