Cod sursa(job #2681008)

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

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

vector <int> bucket[BUCKETS];
int v[MAXN];

void radsort(int v[], int n, int bits){
    if (bits==MAXBITS) return;
    int i, j, ind=0;
    for (i=0; i<n; i++){
        bucket[(v[i]>>bits)&MASK].push_back(v[i]);
    }
    for (i=0; i<BUCKETS; i++){
        for (j=0; j<bucket[i].size(); j++){
            v[ind++]=bucket[i][j];
        }
        bucket[i].clear();
    }
    radsort(v, n, bits+BITS_PER_DIG);
}

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, n, 0);
    for (i=0; i<n; i+=skip) fprintf(fout, "%d ", v[i]);
    return 0;
}