Cod sursa(job #2847548)

Utilizator BalasaRaduBalasa Radu BalasaRadu Data 10 februarie 2022 21:46:33
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int dim=1e7+9;

int fv[300];
int v[2][dim];

signed main(){
    int n,a,b,c;
        fin>>n>>a>>b>>c;
    v[0][1]=b;
    for(int i=2;i<=n;i++){
        v[0][i]=(1LL*a*v[0][i-1]+b)%c;
    }
    int cnt=0;
    for(int base=0;base<=31;base+=8){
        for(int i=1;i<=n;i++){
            int nr=(v[cnt%2][i]>>base)&255;
            fv[nr]++;
        }
        for(int i=1;i<=255;i++){
            fv[i]+=fv[i-1];
        }
        for(int i=n;i>=1;i--){
            int nr=(v[cnt%2][i]>>base)&255;
            v[(cnt+1)%2][fv[nr]]=v[cnt%2][i];
            fv[nr]--;
        }
        fill(fv,fv+256,0);
        cnt++;
    }

    for(int i=1;i<=n;i+=10){
        fout<<v[cnt%2][i]<<' ';
    }
}