Cod sursa(job #1758592)

Utilizator Burbon13Burbon13 Burbon13 Data 17 septembrie 2016 15:16:21
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <queue>
#include <cstdio>

using namespace std;

const int nmx = 10000002;
const long long galeti[] = {255, 255 << 8, 255 << 16, 1LL*255 << 24};
const int shift[] = {0,8,16,24};

int a,b,c,n;
int v[nmx];
queue <int> q[260];

void citire()
{
    scanf("%d %d %d %d", &n, &a, &b, &c);
}

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

int place(int val, int p)
{
    return ((val &  galeti[p]) >> shift[p]);
}

void radix_sort()
{
    for(int i = 0; i < 4; ++i)
    {
        for(int j = 1; j <= n; ++j)
            q[place(v[j],i)].push(v[j]);
        v[0] = 0;
        for(int j = 0; j <= 255; ++j)
            while(not q[j].empty())
            {
                v[++v[0]] = q[j].front();
                q[j].pop();
            }

    }
}

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

int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    citire();
    generare();
    radix_sort();
    afish();
    return 0;
}