Cod sursa(job #2579794)

Utilizator MihclerioVladimir Chim Mihclerio Data 12 martie 2020 20:11:34
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.67 kb

#include<bits/stdc++.h>

using namespace std;

int n,a,b,c,v[10000010],aux[10000010];
int i,t,f[256],ba;
int main()
{
  freopen("radixsort.in","r",stdin);
  freopen("radixsort.out","w",stdout);
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  cin>>n>>a>>b>>c;v[1]=b;
  for(i=2;i<=n;i++) v[i]=(1ll*a*v[i-1]+b)%c;
  for(t=4;t--;)
  {
      for(i=1;i<=n;i++) f[((v[i]>>ba)&255)]++;
      for(i=1;i<=255;i++) f[i]+=f[i-1];
      for(i=n;i>=1;i--) aux[f[(v[i]>>ba)&255]]=v[i],f[(v[i]>>ba)&255]--;
      for(i=1;i<=n;i++) v[i]=aux[i];
      for(i=0;i<=255;i++) f[i]=0;
      ba+=8;
  }
  for(i=1;i<=n;i+=10) cout<<v[i]<<" ";
  return 0;
}