Pagini recente » Cod sursa (job #3128597) | Cod sursa (job #3162494) | Cod sursa (job #2863286) | Cod sursa (job #2158413) | Cod sursa (job #2974003)
//https://www.infoarena.ro/problema/radixsort
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int const MAX = 10000001;
int arr[MAX];
vector <pair<int, pair<int, int>>> buckets[100005];
vector <pair<int, pair<int, int>>> sorted;
void radix(int arr[], int n) {
pair<int, int> keyNumber;
int x = 100000;
for (int i = 1; i <= n; ++i) {
keyNumber.first = int(arr[i] / x);
keyNumber.second = arr[i] % x;
buckets[keyNumber.second].push_back({arr[i], {keyNumber.first, keyNumber.second}});
}
for (int j = 0; j < x; ++j) {
if (buckets[j].empty()) continue;
for (int k = 0; k < buckets[j].size(); ++k) {
sorted.push_back(buckets[j][k]);
}
buckets[j].clear();
}
int condition = 3;
while (condition != 0) {
for (int i = 0; i < n; ++i) {
sorted[i].second.first = int(sorted[i].second.first / 10);
sorted[i].second.second = sorted[i].second.first % 10;
buckets[sorted[i].second.second].push_back({sorted[i].first, {sorted[i].second.first, sorted[i].second.second}});
}
sorted.clear();
for (int l = 0; l <= 9; ++l) {
for (int m = 0; m < buckets[l].size(); ++m) {
sorted.push_back(buckets[l][m]);
}
buckets[l].clear();
}
condition -= 1;
}
}
int main()
{
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int N, A, B, C;
fin >> N >> A >> B >> C;
arr[1] = B;
for (int i = 1; i <= N; ++i) {
arr[i] = (A * arr[i-1] + B) % C;
}
radix(arr, N);
for (int i = 0; i < N; i += 10) {
fout << sorted[i].first << " ";
}
}