Cod sursa(job #3039229)

Utilizator Vlad_NistorNIstor Vlad Vlad_Nistor Data 28 martie 2023 12:22:12
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;
#define BASE 256

int a[10000002], v[10000002], vf[BASE+2];
int main(void){
    ofstream cout("radixsort.out");
    ifstream cin("radixsort.in");
    int n, aa, b , c;
    cin >> n >> aa >> b >> c;
    a[1] = b;
    int maxim = -1;

    for (int i = 2; i<=n; i++) {
        a[i]=(aa *1LL* a[i-1] +b ) % c;
        maxim = max(maxim, a[i]);
    }
    int cifre = 0;
    while(maxim){
        cifre++;
        maxim /= BASE;
    }
    int z = 0;
    for(int c = 1;c <= cifre; c++ ) {
        for(int i = 0;i<BASE;i++){
            vf[i] = 0;
        }

        for (int i = 1; i<=n; i++)
            vf[ (a[i] >> z) & 255]++;

        for (int i=1;i<BASE;i++)
            vf[i] += vf[i-1];

        for(int i= n;i>=1;i--){
            v[vf[ (a[i] >> z)  & 255]-- ] = a[i];
        }

        for(int i = 1;i<=n;i++){
            a[i] = v[i];
        }
        z += 8;
    }
    for(int i = 1;i<=n;i+=10){
        cout << a[i] << ' ';
    }
}