Cod sursa(job #1552269)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 decembrie 2015 17:08:47
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

const int mask = (1<<8)-1;

int v[10000005];
int va[10000005];
int q[mask+5];

int main()
{
    int i,n,A,B,C,mm,c,cnt,m;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d %d %d %d",&n,&A,&B,&C);
    v[1] = B%C;
    for(i = 2;i <= n;i++){
        v[i] = (1LL*A*v[i-1]+B)%C;
    }
    for(int shift = 0;shift < 32;shift += 8){
        for(i = 1;i <= n;i++){
            int k = (v[i]>>shift)&mask;
            q[k]++;
        }
        for(i = 1;i <= mask;i++){
            q[i] += q[i-1];
        }
        for(i = n;i >= 1;i--){
            int k = (v[i]>>shift)&mask;
            va[q[k]] = v[i];
            q[k]--;
        }
        for(i = 1;i <= n;i++){
            v[i] = va[i];
        }
        for(i = 0;i <= mask;i++){
            q[i] = 0;
        }
    }
    for(i = 1;i <= n;i += 10){
        printf("%d ",v[i]);
    }
    return 0;
}