Cod sursa(job #3264919)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 25 decembrie 2024 18:49:18
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define MAX 10000000
#define BUCKET 256
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int n,A,B,C,i,j,v[MAX+5],v2[MAX+5],aux;
int b[260],ind[260];
void clr(){
    for(int i=0;i<260;i++)  b[i] = ind[i] = 0;
}
void Sort(){
    for(i=1;i<=n;i++){
        b[v[i]%BUCKET]++;
    }
    j=1;
    for(i=0;i<BUCKET;i++){
        ind[i] = j;
        j += b[i];
    }
    for(i=1;i<=n;i++){
        v2[ind[v[i]%BUCKET]++] = v[i];
    }
    clr();
    for(i=1;i<=n;i++){
        b[(v2[i]>>8)%BUCKET]++;
    }
    j=1;
    for(i=0;i<BUCKET;i++){
        ind[i] = j;
        j += b[i];
    }
    for(i=1;i<=n;i++){
        v[ind[(v2[i]>>8)%BUCKET]++] = v2[i];
    }
    clr();
    for(i=1;i<=n;i++){
        b[(v[i]>>16)%BUCKET]++;
    }
    j=1;
    for(i=0;i<BUCKET;i++){
        ind[i] = j;
        j += b[i];
    }
    for(i=1;i<=n;i++){
        v2[ind[(v[i]>>16)%BUCKET]++] = v[i];
    }
    clr();
    for(i=1;i<=n;i++){
        b[(v2[i]>>24)%BUCKET]++;
    }
    j=1;
    for(i=0;i<BUCKET;i++){
        ind[i] = j;
        j += b[i];
    }
    for(i=1;i<=n;i++){
        v[ind[(v2[i]>>24)%BUCKET]++] = v2[i];
    }
    clr();
}
int main()
{
    fin>>n>>A>>B>>C;
    v[1] = B;
    for(i=2;i<=n;i++)
        v[i] = (1LL * A * v[i-1] % C + B) % C;
    Sort();
    for(i=1;i<=n;i+=10)
        fout<<v[i]<<' ';
    return 0;
}