Cod sursa(job #2617377)

Utilizator DiagrDiana Grigore Diagr Data 21 mai 2020 16:13:54
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
int n, a, b, c;
int v[10000001];

void countsort(int A[], int B[], int k){
    int count[256];
    int index[256];
    for (int i = 0; i <= 255; i++)
        count[i] = 0;
    for (int i = 0; i < n; i++)
        count[A[i] >> (k * 8) & 255]++;
    index[0] = 0;
    for (int i = 1; i < 256; i++)
        index[i] = index[i - 1] + count[i - 1];
    for (int i = 0; i < n; i++)
        B[index[A[i] >> (k * 8)& 255]++] = A[i];

}

void radixsort(){
    int *temp = new int[n];
    for (int i = 0; i < sizeof(v[0]); i++)
        if (i % 2 == 0)
            countsort(v, temp, i);
        else
            countsort(temp, v, i);
}


int main() {
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b >> c;
    v[0] = b;
    for (int i = 1; i < n; i++)
        v[i] = (1LL* a * v[i - 1] + b) % c;
    radixsort();
    for (auto i = 0; i < n; i+=10)
        cout << v[i] << " ";
    return 0;
}