Pagini recente » Borderou de evaluare (job #2201503) | Borderou de evaluare (job #520099) | Cod sursa (job #806179) | Cod sursa (job #2621017) | Cod sursa (job #2654322)
#include <fstream>
#include <array>
using namespace std;
const uint MAXN = 10000000;
const uint USED_BITS = 31;
const uint RADIX_BITS = 11;
const uint RADIX = 1 << RADIX_BITS;
uint buf1[MAXN];
uint buf2[MAXN];
uint buckets[RADIX];
uint* radixsort(uint N, uint *vect)
{
uint *temp = buf2;
for (uint step = 0; step < USED_BITS; step += RADIX_BITS) {
for (uint i = 0; i < RADIX; ++i)
buckets[i] = 0;
for (uint i = 0; i < N; ++i)
++buckets[(vect[i] >> step) & (RADIX-1)];
for (uint i = 1; i < RADIX; ++i)
buckets[i] += buckets[i-1];
for (int i = N-1; i != -1; --i)
{
uint b = (vect[i] >> step) & (RADIX-1);
--buckets[b];
temp[buckets[b]] = vect[i];
}
swap(vect, temp);
}
return vect;
}
int main(int argc, char const *argv[])
{
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
unsigned long long N, A, B, C;
fin >> N >> A >> B >> C;
buf1[0] = B;
for (uint i = 1; i < N; i++)
{
buf1[i] = (((A * buf1[i-1]) % C + B) % C);
}
uint* vect = radixsort(N, buf1);
for (uint i = 0; i < N; i += 10)
fout << vect[i] << ' ';
return 0;
}