Cod sursa(job #2817865)

Utilizator ElizaTElla Rose ElizaT Data 14 decembrie 2021 13:20:29
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#define NMAX 10000002
#define BASE (1<<8)
#define MASK (BASE-1)

using namespace std;

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

int n,a,b,c;
int v[NMAX],aux[NMAX];
int cnt[BASE],ind[BASE];

void radix_sort(int n, int b, int v[], int aux[]) {
    if (b != 32) {
        for(int i = 0;i < BASE;i++)
            cnt[i] = 0;
        for(int i = 0;i < n;i++)
            cnt[((v[i] >> b) & (MASK))]++;
        ind[0] = 0;
        for(int i = 1;i < BASE;i++)
            ind[i] = ind[i - 1] + cnt[i - 1];
        for(int i = 0;i < n;i++)
            aux[ind[((v[i] >> b) & (MASK))]++] = v[i];
        radix_sort(n, b + 8, aux, v);
    }
}

int main()
{
    fin >> n >> a >> b >> c;
    v[0] = b;
    for(int i = 1;i < n;i++)
        v[i] = ((long long)a * v[i - 1] + b) % c;
    radix_sort(n, 0, v, aux);
    for(int i = 0;i < n;i += 10)
        fout << v[i] << ' ';
    fout << '\n';
    return 0;
}