Cod sursa(job #2278573)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 8 noiembrie 2018 11:22:31
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#define MAX 10000010
#define MOD 256

using namespace std;
typedef long long ll;

ll n,a,b,c;
int va[MAX],vb[MAX],sp[MOD],pa[MOD];
void sorteaza(int v1[MAX],int v2[MAX],int sh){
  int sz=0,md,ei;
  for(int i=0;i<MOD;i++)sp[i]=pa[i]=0;
  for(int i=1;i<=n;i++)
    sp[((v1[i]>>sh)&(MOD-1))]++;
  for(int i=1;i<MOD;i++)sp[i]+=sp[i-1];
  for(int i=1;i<=n;i++){
    md=((v1[i]>>sh)&(MOD-1));
    if(md==0)ei=0; else ei=sp[md-1];
    v2[ei+(++pa[md])]=v1[i];
  }
}

int main()
{
    ifstream f ("radixsort.in");
    ofstream g ("radixsort.out");
    f>>n>>a>>b>>c;
    va[1]=b;
    for(int i=2;i<=n;i++)
      va[i]=(a*va[i-1]+b)%c;
    for(int sh=0;sh<31;sh+=8)
      if((sh/8)%2==0)
        sorteaza(va,vb,sh);
      else
        sorteaza(vb,va,sh);
    for(int i=1;i<=n;i+=10)
      g<<va[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}