Pagini recente » Cod sursa (job #1532480) | Cod sursa (job #2743704) | Cod sursa (job #1001059) | Cod sursa (job #2108552) | Cod sursa (job #2434981)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector<int> arr, helper;
int cnt[10];
void countingSort(int digitIndex)
{
memset(cnt, 0, sizeof cnt);
for (int num : arr)
{
cnt[(num / digitIndex) % 10]++;
}
for (int i = 1; i < 10; i++)
{
cnt[i] += cnt[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--)
{
helper[cnt[(arr[i] / digitIndex) % 10] - 1] = arr[i];
cnt[(arr[i] / digitIndex) % 10]--;
}
arr = helper;
}
void radixSort()
{
int maxElem = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxElem / exp > 0; exp *= 10)
{
countingSort(exp);
}
}
int main()
{
int N, A, B, C;
fin >> N >> A >> B >> C;
arr.push_back(B%C);
for (int i = 1; i < N; i++)
{
arr.push_back((1LL * A*arr.back() + B) % C);
}
helper = arr;
radixSort();
for (int i = 0; i < N; i +=10)
{
fout << arr[i] << " ";
}
return 0;
}