Cod sursa(job #3175781)

Utilizator Andrei_Gagea08Andrei Gagea Andrei_Gagea08 Data 26 noiembrie 2023 13:30:35
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include<iostream>
#include <cstring>

#define BPS 4
#define MB 32
#define MOD 15

using namespace std;

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

int v[10000001];
int vm[10000001];
int n;
long long a,b,c;

void gen()
{
   v[1]=b;
   for(int i=2;i<=n;i++)
      v[i] = 1LL * (1LL * a * v[i-1] + b) % c;
}
void afis(int p)
{
   for(int i=1;i<=n;i+=p)
      out<<v[i]<<" ";
}

int rec(int *f,int p)
{
   if(p==0)
   {
      int aux=f[0];
      f[0]=0;
      return aux;
   }
   else
   {
      int aux=f[p];
      f[p]=rec(f,p-1);
      if(f[p]!=0)
         f[p]++;
      return f[p]+aux-1;
   }
}


void radix(int l,int r,int bit)
{
   if(l<r && bit>0)
   {
      int f[16];
      ///cerr<<l<<" "<<r<<'\n';
      int i;
      bit-=BPS;
      memset(f,0,sizeof(f));
      for(i=l;i<=r;i++)
          f[v[i] >> bit & MOD]++ , vm[i]=v[i];

      ///for(i=0;i<=15;i++)
         ///cerr<<f[i]<<" ";
      ///cerr<<endl;
      rec(f,15);
      ///for(i=0;i<=15;i++)
         ///cerr<<f[i]<<" ";
      ///cerr<<endl;
      for(i=l;i<=r;i++)
      {
         v[f[vm[i]>>bit&MOD]+l]=vm[i];
         f[vm[i]>>bit&MOD]++;
      }

      /// f[x]+l = prima poz pe care nu am pus
      radix(l,l+f[0]-1,bit);
      for(i=1;i<16;i++)
         radix(l+f[i-1],l+f[i]-1,bit);
   }
}

int main()
{
    in>>n>>a>>b>>c;
    v[1]=b;
    gen();

    radix(1,n,MB);
    afis(10);
    return 0;
}