Cod sursa(job #3205004)

Utilizator gianiferSpita Alexandru-Mihai gianifer Data 18 februarie 2024 16:42:39
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define N_MAX 10000005
using namespace std;

ifstream fin("radixsort.in");

ofstream fout("radixsort.out");

const int mask = (1 << 8) - 1;

const int maxim = 8;

int salvare[N_MAX];

int n, a, b, c;

int v[N_MAX];

int main()
{
    fin >> n >> a >> b >> c;
    v[1] = b;
    for (int i = 2; i <= n; i++)
    {
        v[i] = (1LL * a * v[i - 1] + b) % c;
    }
    for (int imp = 0; imp <= 31; imp += maxim)
    {
        int frecventa[mask + 1];
        int pozitii[mask + 1];
        pozitii[0] = 1;
        memset(frecventa, 0, sizeof(frecventa));
        for (int i = 1; i <= n; i++)
        {
            frecventa[(v[i] >> imp) & mask]++;
        }
        for (int i = 1; i <= mask; i++)
            pozitii[i] = pozitii[i - 1] + frecventa[i - 1];
        for (int i = 1; i <= n; i++)
        {
            salvare[pozitii[(v[i] >> imp) & mask]++] = v[i];
        }
        swap(salvare, v);
    }
    for (int i = 1; i <= n; i += 10)
        fout << v[i] << " ";
}