Cod sursa(job #2817842)

Utilizator ElizaTElla Rose ElizaT Data 14 decembrie 2021 12:34:26
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

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

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