Cod sursa(job #2607442)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 29 aprilie 2020 19:14:44
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb

#include <bits/stdc++.h>
using namespace std;

const int N = (1 << 8);
const int mask = (1 << 8) - 1;
const int DMAX = 10000000;
int sz[N], A[DMAX], B[DMAX];


void RSort(int from[], int t[], int dim, int sham)
{
    fill(sz, sz + N, 0);
    for (int i = 0; i < dim; i++)
        sz[(from[i] >> sham) & mask]++;
    
    for (int i = 1; i < N; i++)
        sz[i] += sz[i - 1];

    for (int i = dim - 1; i >= 0; i--)
        t[--sz[(from[i] >> sham) & mask]] = from[i];
}

int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    
    int n, a, b, c;
    in >> n >> a >> b >> c;
    
    A[0] = b;
    for (int i = 1; i < n; i++)
        A[i] = (1LL * A[i - 1] * a + b) % c;

    RSort(A, B, n, 0);
    RSort(B, A, n, 8);
    RSort(A, B, n, 16);
    RSort(B, A, n, 24);

    for (int i = 1; i < n; i++)
        assert(A[i] >= A[i - 1]);

    for (int i = 0; i < n; i += 10)
        out << A[i] << ' ';
    
    out << '\n';
    return 0;
}