Cod sursa(job #2693745)

Utilizator SerbaP123Popescu Serban SerbaP123 Data 6 ianuarie 2021 21:41:24
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>
#include <map>
#define nmax (int) 1e7
using namespace std;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

vector <int> arr;
int frequency[nmax], sortHigh[nmax];

int main(){
    int nNumbers, a, b, c, maxHigh = 0;
    cin >> nNumbers >> a >> b >> c;
    arr.push_back(b);
    for(int i = 1; i < nNumbers; ++i){
        int result = (a * arr[i - 1] + b) % c;
        arr.push_back(result);
    }
    for(int i = 0; i < nNumbers; ++i){
        if(arr[i] > maxHigh){
            maxHigh = arr[i];
        }
    }
    for(int i = 0; i < nNumbers; ++i){
        frequency[arr[i]]++;
    }
    for(int i = 1; i < maxHigh - 1; ++i){
        frequency[i] += frequency[i - 1];
    }
    for(int i = nNumbers - 1; i >= 0; --i){
        sortHigh[--frequency[arr[i]]] = arr[i];
    }
    for(int i = 0; i < nNumbers; i += 10){
        cout << sortHigh[i] << " ";
    }
    return 0;
}