Cod sursa(job #1970454)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 19 aprilie 2017 12:54:31
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<cstdio>

using namespace std;

const int bucket = 8;
const int lim = (1 << 8) - 1;
const int NMAX = 10000000;

int n, a, b, c;
int v[1 + NMAX];
int temp[1 + NMAX];
int vis[1 + lim];
int pos[1 + lim];

int get_bucket(int nr, int id)
{
    return ((nr >> (id * bucket)) & lim);
}

void clear_vis()
{
    for(int i = 0; i <= lim; i++)
    {
        vis[i] = 0;
    }
}

void radix(int id)
{
    clear_vis();

    for(int i = 1; i <= n; i++)
    {
        vis[get_bucket(v[i], id)]++;
    }

    for(int i = 1; i <= lim; i++)
    {
        vis[i] += vis[i - 1];
    }

    for(int i = n; i >= 1; i--)
    {
        temp[vis[get_bucket(v[i], id)]] = v[i];
        vis[get_bucket(v[i], id)]--;
    }

    for(int i = 1; i <= n; i++)
    {
        v[i] = temp[i];
    }
}

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);

    scanf("%d %d %d %d", &n, &a, &b, &c);

    v[1] = b;
    for(int i = 2; i <= n; i++)
    {
        v[i] = (1LL * a * v[i-1] + b) % c;
    }

    int to = 32 / bucket;
    for(int i = 0; i < to; i++)
    {
        radix(i);
    }

    for(int i = 1; i <= n; i += 10)
    {
        printf("%d ", v[i]);
    }
}