Cod sursa(job #1521910)

Utilizator sebinechitasebi nechita sebinechita Data 10 noiembrie 2015 22:49:26
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
#define MAX 10000100
#define imp(i, ki) ((a[(ki) & 1][(i)] >> ((ki) << 3)) & ((1<<8) - 1))
int a[2][MAX];
int fr[(1<<8) + 3];

int main()
{
    int n, A, B, C, i, ki;
    fin >> n >> A >> B >> C;
    a[0][1] = B;
    for(i = 2 ; i <= n ; i++)
        a[0][i] = (1ll * a[0][i - 1] * A + B) % C;
    for(ki = 0 ; ki < 4 ; ki++)
    {
        for(i = 1 ; i <= n ; i++)
            fr[imp(i, ki)]++;
        for(i = 1 ; i < (1<<8) ; i++)
            fr[i] += fr[i - 1];
        for(i = n ; i >= 1 ; i--)
            a[(ki + 1) & 1][fr[imp(i, ki)]--] = a[ki & 1][i];
        for(i = 0 ; i < (1 << 8) ; i++)
            fr[i] = 0;
    }
    for(i = 1 ; i <= n ; i += 10)
        fout << a[0][i] << " ";
    fout << "\n";
}