Cod sursa(job #2683182)

Utilizator DordeDorde Matei Dorde Data 10 decembrie 2020 17:03:03
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
using namespace std;
int const N = 1e7 + 1;
int v [N] , v2 [N];
void rsort (int v [] , int v2 [] , int n , int bits){
    static int fq [(1 << 8) + 1];
    int mask = (1 << 8) - 1 , mx = 0;
    if (bits == 32)
        return;
    fill (fq , fq + 1 + mask , 0);
    for(int i = 0 ; i < n ; ++ i){
        int nr = (v [i] >> bits) & mask;
        ++ fq [nr];
        mx = max (mx , nr);
    }
    static int ind [(1 << 8) + 1];
    ind [0] = 0;
    for(int i = 1 ; i <= mx ; ++ i)
        ind [i] = fq [i - 1] + ind [i - 1];
    for(int i = 0 ; i < n ; ++ i){
        int nr = (v [i] >> bits) & mask;
        v2 [ind [nr] ++] = v [i];
    }
    rsort (v2 , v , n , bits + 8);
}
ifstream cin ("radix.in");
ofstream cout ("radix.out");
int main()
{
    int n , a , b , c;
    cin >> n >> a >> b >> c;
    v [0] = b;
    for(int i = 1 ; i < n ; ++ i)
        v [i] = (1LL * a * v [i - 1] + b) % c;
    rsort (v , v2 , n , 0);
    for(int i = 0 ; i < n ; i += 10)
        cout << v [i] << ' ';
    return 0;
}