Cod sursa(job #2607430)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 29 aprilie 2020 19:03:20
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb

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

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


void RSort(int from[], int t[], int dim, int sham, int dir)
{
    fill(head, head + N, -1);
    for (int i = 0; i < dim; i++) {
        int v = (from[i] >> sham) & mask;
        urm[i] = head[v];
        head[v] = i;
    }
    if (dir) {
        dim = 0;
        for (int i = 0; i < N; i++) {
            while (head[i] != -1) {
                t[dim++] = from[head[i]];
                head[i] = urm[head[i]];
            }
        }
    }
    else {
        dim = 0;
        for (int i = N - 1; i >= 0; i--) {
            while (head[i] != -1) {
                t[dim++] = from[head[i]];
                head[i] = urm[head[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, false);
    RSort(B, A, n, 8, true);
    RSort(A, B, n, 16, false);
    RSort(B, A, n, 24, true);

    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;
}