Pagini recente » Cod sursa (job #2772979) | Cod sursa (job #503578) | Cod sursa (job #1273056) | Cod sursa (job #3031142) | Cod sursa (job #1736925)
#include <bits/stdc++.h>
using namespace std;
class RadixSort
{
private:
static const int MAX_DIGITS = 8;
static const int RADIX = (1 << MAX_DIGITS);
static const int MASK = RADIX - 1;
public:
static void sort(vector<int> &A)
{
vector<int> B(A.size());
vector<int> buckets(RADIX);
const int N = A.size();
for (int shift = 0; shift < 32; shift += MAX_DIGITS)
{
fill(buckets.begin(), buckets.end(), 0);
for (int v : A)
++buckets[(v >> shift) & MASK];
partial_sum(buckets.begin(), buckets.end(), buckets.begin());
for (int i = N - 1; i >= 0; --i)
B[--buckets[(A[i] >> shift) & MASK]] = A[i];
copy(B.begin(), B.end(), A.begin());
}
}
};
void printNumber(int nr, string &output)
{
char digits[10];
int n = 0;
do
{
digits[n++] = '0' + nr % 10;
nr /= 10;
} while (nr > 0);
for (int i = n - 1; i >= 0; i--)
output += digits[i];
output += " ";
}
int main()
{
ifstream in("radixsort.in");
ofstream out("radixsort.out");
int N, A, B, C;
in >> N >> A >> B >> C;
vector<int> v(N);
v[0] = B;
for (int i = 1; i < N; ++i)
{
int t = (1LL * A * v[i - 1] + B) % C;
v[i] = t;
}
RadixSort::sort(v);
string output;
for (int i = 0; i < N; i += 10)
printNumber(v[i], output);
out << output << endl;
return 0;
}