Cod sursa(job #2681026)

Utilizator andrei_ciobanuciobanu andrei andrei_ciobanu Data 4 decembrie 2020 20:05:24
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;
#define MAXN 10000000
#define MAXBITS 32
#define DIGIT_SIZE 4
#define BUCKETS (1<<DIGIT_SIZE)
#define MASK ((1<<DIGIT_SIZE)-1)

vector <int> bucket[BUCKETS];
int v[MAXN], v_aux[MAXN], freq[BUCKETS], ind[BUCKETS];

int find_bucket(int x, int bits){
    return (x>>bits)&MASK;
}

void radsort(int v[], int v_aux[], int n, int bits){
    if (bits==MAXBITS) return;
    int i;
    for (i=0; i<BUCKETS; i++) freq[i]=0;
    for (i=0; i<n; i++){
        freq[find_bucket(v[i], bits)]++;
    }
    ind[0]=0;
    for (i=1; i<BUCKETS; i++) ind[i]=ind[i-1]+freq[i-1];

    for (i=0; i<n; i++){
        v_aux[ind[find_bucket(v[i], bits)]++]=v[i];
    }
    radsort(v_aux, v, n, bits+DIGIT_SIZE);
}

int main()
{
    FILE *fin=fopen("radixsort.in", "r");
    FILE *fout=fopen("radixsort.out", "w");
    int n, a, b, c;
    fscanf(fin, "%d%d%d%d", &n, &a, &b, &c);
    const int A=a, B=b, C=c, skip=10;
    v[0]=B;
    int i;
    for (i=1; i<n; i++){
        v[i]=(long long int)(A*v[i-1]+B)%C;
    }
    radsort(v, v_aux, n, 0);
    for (i=0; i<n; i+=skip) fprintf(fout, "%d ", v[i]);
    return 0;
}