Cod sursa(job #1557283)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 27 decembrie 2015 09:38:13
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <cstdio>
#define nmax 10000005
#include <vector>
#include <cstring>
#define RADIX 0xff

using namespace std;

int N,A,B,C,v[nmax];
vector <int> G[12];

void countsort(int a[],int b[],int byte){
    int counter[1<<8];
    int index[1<<8];
    int i;

    memset(counter,0,sizeof(counter));

    for(i = 0;i < N;++i)
        ++counter[((a[i] >> (byte * 8))&RADIX)];

    index[0] = 0;
    for(i = 1;i < 1<<8;++i)
        index[i] = index[i-1] + counter[i-1];

    for(i = 0;i < N;++i)
        b[index[(a[i]>>(byte * 8))&RADIX]++] = a[i];
}

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

    scanf("%d %d %d %d",&N,&A,&B,&C);
    v[0] = B;
    int i;
    for(i = 1;i<N;++i)
        v[i] = (1LL * A * v[i-1] + B) % C;

    int *temp = new int[N+1];
    for(i = 0;i < sizeof(v[0]);++i){
        if(i%2 == 0)countsort(v,temp,i);
        else countsort(temp,v,i);
    }

    for(i=0;i < N;i+=10)printf("%d ",v[i]);
    printf("\n");

    return 0;
}