Cod sursa(job #2485093)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 31 octombrie 2019 22:55:17
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define MAXDIGIT 10

int count_digits(int n) {
    if (n < 0) {
        return count_digits(-n);
    }

    if (n < 10) {
        return 1;    
    }

    return 1 + count_digits(n / 10);
}

void radix_sort(std::vector<int>& v) {

    auto maxelem_it = std::max_element(v.begin(), v.end());
    int steps = count_digits(*maxelem_it);


    std::queue<int> q[10];
    int power = 1;
    for (int k = 1; k <= steps; ++k, power *= 10) {
        for (int x : v) {
            int qindex = (x / power) % 10;
            q[qindex].push(x);
        }

        int cnt = 0;
        for (int i = 0; i < 10; ++i) {
            while (!q[i].empty()) {
                v[cnt++] = q[i].front();
                q[i].pop();
            }
        }
    }
}

int main() {
	std::ifstream in("radixsort.in");
	std::ofstream out("radixsort.out");

	int n, a, b, c;
	in >> n >> a >> b >> c;

	std::vector<int> arr;
	arr.push_back(b);
	
	for (int i = 1; i < n; ++i) {
		arr.push_back(1LL * (a * arr[i - 1] + b) % c);
	}

	radix_sort(arr);

	for (int i = 0; i < n; i += 10) {
		out << arr[i] << ' ';
	}

	return 0;
}