Cod sursa(job #3264913)

Utilizator nicushor21Pirlog Marian Nicolae nicushor21 Data 25 decembrie 2024 18:34:10
Problema Radix Sort Scor 0
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;
vector <int> b[260];
void clr(){
    for(int i=0;i<260;i++)  b[i].clear();
}
void Sort(){
    for(i=n;i>0;i--){
        b[(v[i]>>24)%BUCKET].push_back(i);
    }
    j=0;
    for(i=0;i<BUCKET;i++){
        while(!b[i].empty()){
            v2[++j] = v[b[i].back()];
            b[i].pop_back();
        }
    }
    clr();
    for(i=n;i>0;i--){
        b[(v2[i]>>16)%BUCKET].push_back(i);
    }
    j=0;
    for(i=0;i<BUCKET;i++){
        while(!b[i].empty()){
            v[++j] = v2[b[i].back()];
            b[i].pop_back();
        }
    }
    clr();
    for(i=n;i>0;i--){
        b[(v[i]>>8)%BUCKET].push_back(i);
    }
    j=0;
    for(i=0;i<BUCKET;i++){
        while(!b[i].empty()){
            v2[++j] = v[b[i].back()];
            b[i].pop_back();
        }
    }
    clr();
    for(i=n;i>0;i--){
        b[v2[i]%BUCKET].push_back(i);
    }
    j=0;
    for(i=0;i<BUCKET;i++){
        while(!b[i].empty()){
            v[++j] = v2[b[i].back()];
            b[i].pop_back();
        }
    }
}
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;
}