Cod sursa(job #2626105)

Utilizator stefanst77Luca Stefan Ioan stefanst77 Data 6 iunie 2020 11:54:38
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

vector<int> a;

void CountSort_RadixSort(int cifra, int baza)
{
    vector<int> aux (a.size(), 0);
    vector<int> c(baza, 0);
    int i;

    for (i = 0; i < int(a.size()); i++)
        c[ (a[i]/cifra) % baza ]++;

    for (i = 1; i < baza; i++)
        c[i] += c[i - 1];

    for (i = int(a.size() - 1); i >= 0; i--)
    {
        aux[ c[ (a[i]/cifra) % baza] - 1] = a[i];
        c[ (a[i]/cifra) % baza]--;
    }

    for (i = 0; i < int(a.size()); i++)
        a[i] = aux[i];
}

void RadixSort(int baza)
{
    int i, mx = -1;
    for(i = 0; i < int(a.size()); i++)
        if (a[i] > mx)
            mx = a[i];

    for (int cifra = 1; mx / cifra > 0; cifra *= baza)
        CountSort_RadixSort(cifra, baza);
}

void Afisare(vector<int> q)
{
    for (vector<int>::iterator it = q.begin(); it != q.end(); it += 10)
        fout << *it << " ";
    fout << "\n";
}

int main()
{
    long long n, A, B, C, pred;
    int x;
    fin >> n >> A >> B >> C;
    a.push_back(B);
    pred = B;
    for (int i = 1; i < n; i++)
    {
        x = (A * pred + B) % C;
        a.push_back(x);
        pred = x;
    }
    RadixSort(256);
    Afisare(a);
    fin.close();
    fout.close();
    return 0;
}