Pagini recente » Monitorul de evaluare | Clasament cool_bc | Clasament concurs_2014 | Flux si cuplaj | Cod sursa (job #2434979)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector<int> arr, helper;
void countingSort(int digitIndex)
{
int count[10];
memset(count, 0, sizeof count);
for (int num : arr)
{
count[(num / digitIndex) % 10]++;
}
for (int i = 1; i < 10; i++)
{
count[i] += count[i - 1];
}
for (int i = arr.size() - 1; i >= 0; i--)
{
helper[count[(arr[i] / digitIndex) % 10] - 1] = arr[i];
count[(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((arr.back() * A + B) % C);
}
helper = arr;
radixSort();
for (int i = 0; i < N; i +=10)
{
fout << arr[i] << " ";
}
return 0;
}