Cod sursa(job #2817847)

Utilizator ElizaTElla Rose ElizaT Data 14 decembrie 2021 12:43:01
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>

using namespace std;

const int NMAX = 1e7,BUCKET = (1 << 8) - 1;
int v[NMAX + 5],cnt[(1 << 8)],cnt1[(1 << 8)],aux[NMAX + 5];
int n;

void init() {
    for (int i = 0;i <= BUCKET;i++)
        cnt[i] = 0;
}
void count_sort(int *a, int *b, int byte) {
    for (int i = 0;i < n;i++)
        cnt[((a[i] >> byte) & BUCKET)]++;
    cnt1[0] = 0;
    for (int i = 1;i <= BUCKET;i++)
        cnt1[i] = cnt1[i - 1] + cnt[i - 1];
    for (int i = 0;i < n;i++)
        b[cnt1[((a[i] >> byte) & BUCKET)]++] = a[i];
    init();
}
void radix_sort() {
    for (int i = 0;i < 4;i++) {
        if (i % 2 == 0)
            count_sort(v, aux, (i << 3));
        else
            count_sort(aux, v, (i << 3));
    }
}
int main()
{
    ifstream fin("radixsort.in");
    ofstream fout("radixsort.out");
    int b,c,a;
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fin >> n >> a >> b >> c;
    v[0] = b % c;
    for (int i = 1;i < n;i++)
        v[i] = (1ll * a * v[i - 1] % c + b) % c;
    radix_sort();
    for (int i = 0;i < n;i += 10)
        fout << v[i] << " ";
    return 0;
}