Cod sursa(job #3152016)

Utilizator TeddyDinutaDinuta Eduard Stefan TeddyDinuta Data 23 septembrie 2023 15:47:56
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
int n, a, b, c;
int v[10000005];
int tmp[10000005];

void countsort(int a[], int b[], int byte) {
    int counter[(1 << 8) + 1];
    int start[(1 << 8) + 1];
    memset(counter, 0, sizeof(counter));

    for (int i = 1; i <= n; i++)
        counter[(a[i] >> (byte * 8)) & 0xff]++;

    start[0] = 0;
    for (int i = 1; i < (1 << 8); i++)
        start[i] = start[i - 1] + counter[i - 1];

    for (int i = 1; i <= n; i++)
        b[++start[(a[i] >> (byte * 8)) & 0xff]] = a[i];
}

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

    for (int i = 0; i < 4; i++)
        if (i % 2 == 0)
            countsort(v, tmp, i);
        else
            countsort(tmp, v, i);

    for (int i = 1; i <= n; i += 10)
        out << v[i] << " ";
    return 0;
}