Cod sursa(job #2776407)

Utilizator sirbu_andreiSirbu Andrei sirbu_andrei Data 19 septembrie 2021 17:00:58
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

void countSort(vector<int>& nums, int exp) {

    vector<int> output(nums.size());
    int cnt[10] = { 0 };

    for (int i = 0; i < nums.size(); i++)
        cnt[(nums[i] / exp) % 10] ++;

    for (int i = 1; i < 10; i++)
        cnt[i] += cnt[i - 1];

    for (int i = nums.size() - 1; i >= 0; i--) {
        output[cnt[(nums[i] / exp) % 10]- 1] = nums[i];
        cnt[(nums[i] / exp) % 10] --;
    }

    for (int i = 0; i < nums.size(); i++)
        nums[i] = output[i];
}

void radixSort(vector<int>& nums) {

    int m = *max_element(nums.begin(), nums.end());

    for (int exp = 1; m / exp > 0; exp *= 10)
        countSort(nums, exp);
}

int main(){

    int N, A, B, C;

    f >> N >> A >> B >> C;

    vector<int> numbers(N);

    numbers[0] = B % C;
    for(int i = 1; i < N; i ++)
        numbers[i] = (1LL * A * numbers[i-1] % C + B) % C;

    radixSort(numbers);
    for(int i = 0; i < N; i += 10)
        g << numbers[i] << ' ';
}