Cod sursa(job #1623397)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 1 martie 2016 19:15:32
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long unsigned
#define pb push_back
#define mp make_pair

const int mask = (1<<8)-1;
int v[10000005];
int va[10000005];
int bucket[mask];

int main(){
    int i,n,a,b,c;
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    scanf("%d %d %d %d",&n,&a,&b,&c);
    v[1] = b;
    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;
            bucket[k]++;
        }
        for(i = 0;i <= mask;i++){
            bucket[i] += bucket[i-1];
        }
        for(i = n;i >= 1;i--){
            int k = (v[i]>>shift)&mask;
            va[bucket[k]--] = v[i];
        }
        for(i = 0;i <= mask;i++){
            bucket[i] = 0;
        }
        for(i = 1;i <= n;i++){
            v[i] = va[i];
        }
    }
    for(i = 1;i <= n;i += 10){
        printf("%d ",v[i]);
    }
    return 0;
}