Cod sursa(job #1451493)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 17 iunie 2015 12:20:38
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <stdio.h>
#define Val (V[i] & BM) >> L
using namespace std;

const int Dim = 10000005;
const int Cif = 270;

int A,B,C,N;
int V[Dim],AUX[Dim],Sum[Cif],Cnt[Cif];

void Sort(int L,int R)
{
    int BM = 0;

    for (int i = L;i <= R;i++)
        BM |= 1 << i;

    for (int i = 0;i <= Cif;i++)
    {
        Cnt[i] = 0;
        Sum[i] = 0;
    }

    for (int i = 1;i <= N;i++)
    {
        AUX[i] = V[i];
        Sum[Val]++;
    }

    for (int i = 1;i <= Cif;i++)
        Sum[i] += Sum[i-1];

    for (int i = 1;i <= N;i++)
    {
        int V2 = (AUX[i] & BM) >> L;

        Cnt[V2]++;

        if (V2)
            V[Sum[V2 - 1] + Cnt[V2]] = AUX[i];
        else
            V[Cnt[V2]] = AUX[i];

    }
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

     scanf("%d%d%d%d",&N,&A,&B,&C);

     V[1] = B;

      for (int i = 2;i <= N;i++)
        V[i] = (1LL * A * V[i-1] + B) % C;

      Sort(0,7);
      Sort(8,15);
      Sort(16,23);
      Sort(24,31);

      for (int i = 1;i <= N;i += 10)
        printf("%d ",V[i]);

      printf("\n");
    return 0;
}