Cod sursa(job #2271351)

Utilizator marian013Giugioiu Marian Constantin marian013 Data 28 octombrie 2018 14:11:25
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
using namespace std;
#define RADIX 0xFF
#define get_byte(x) ((x>>(byte * 8))&RADIX)
int n, v[10000002];
void countsort(int A[], int B[], int byte) {
    int i;
    int counter[257];
    int index[256];
    for(i=0;i<256;i++)
        counter[i]=0;
    for(int i = 0; i < n; i ++)
        ++counter[get_byte(A[i])];

    index[0] = 0;

    for(int i = 1; i < 256; i ++)
        index[i] = index[i-1] + counter[i-1];

    for(int i = 0; i < n; i ++)
        B[index[get_byte(A[i])]++] = A[i];
}
void radixsort() {
    int *temp = new int[n];
    for (int i = 0; i < 32; i ++) {
        if(i % 2 == 0)
            countsort(v, temp, i);
        else
            countsort(temp, v, i);
    }
}
int main()
{
    int a, b, c, i;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[0] = b % c;
    for(i = 1; i < n; i++)
        v[i] = (1ll * a * v[i-1] % c + b) % c;
    radixsort();
    for(i = 0; i < n; i+=10)
    printf("%d ",v[i]);
    printf("%d",(int)RADIX);
}