Nu exista pagina, dar poti sa o creezi ...

Cod sursa(job #2955016)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 15 decembrie 2022 22:19:40
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 10000000;
const long long HASH = 128; ///Putem sorta dupa cifre si in alte baze. Aici folosim baza = HASH.

int n;
int v[1 + NMAX];
int aux[1 + NMAX];

int cifre[HASH];

void sortAux(long long putereHash)
{
    for (int i = 0; i < HASH; i++)
        cifre[i] = 0;

    for (int i = 1; i <= n; i++)
        cifre[v[i] / putereHash % HASH]++;

    for (int i = 1; i < HASH; i++)
        cifre[i] += cifre[i - 1];

    for (int i = n; i >= 1; i--)
    {
        aux[cifre[(v[i] / putereHash) % HASH]] = v[i];
        cifre[(v[i] / putereHash) % HASH]--;
    }

    for (int i = 1; i <= n; i++)
        v[i] = aux[i];
}

void radixSort()
{
    int maxim = -1;
    for (int i = 1; i <= n; i++)
        maxim = max(maxim, v[i]);

    for (long long putereHash = 1; putereHash <= maxim; putereHash *= HASH)
        sortAux(putereHash);
}

int main()
{
    ios_base::sync_with_stdio(false);

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

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

    v[1] = b;

    for (int i = 2; i <= n; i++)
        v[i] = (a * v[i - 1] + b) % c;

    radixSort();

    for (int i = 1; i <= n; i += 10)
        out << v[i] << ' ';
    out << '\n';

    in.close();
    out.close();

    return 0;
}