Cod sursa(job #2001436)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 16 iulie 2017 17:39:14
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");

const int NMAX = 1e7 + 5;
const int bits = 8;

int v[NMAX],aux[NMAX],f[1<<bits],N,A,B,C;

void read()
{

    in>>N>>A>>B>>C;
    v[1] = B;
    for(int i = 2 ; i <= N ; ++i)
        v[i] = (1LL*A*v[i-1] + 1LL*B)%C;
}

int get_bucket(int num,int nr)
{

    return (((1 << bits) - 1) << (bits*(nr-1))) & num;
}

void countSort(int bucket)
{

    for(int i = 0 ; i < 1 << bits ; ++i)
        f[i] = 0;
    for(int i = 1 ; i <= N ; ++i)
        f[get_bucket(v[i],bucket)] ++;
    for(int i = 1 ; i < 1 << bits ; ++i)
        f[i] += f[i-1];
    for(int i = N ; i > 0 ; --i){
        aux[f[get_bucket(v[i],bucket)]] = v[i];
        f[get_bucket(v[i],bucket)] --;
    }
    for(int i = 1 ; i <= N ; ++i)
        v[i] = aux[i];
}

void radixSort()
{

    for(int i = 1 ; i <= 4 ; ++i)
        countSort(i);
}

void afis()
{

    for(int i = 1 ; i <= N ; i += 10)
        out<<v[i]<<" ";
}

int main()
{

    read();
    radixSort();
    afis();
    return 0;
}