Cod sursa(job #2136084)

Utilizator DanizisSpartanulDani Mocanu DanizisSpartanul Data 19 februarie 2018 17:08:03
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>

#define NMax 10000005

using namespace std;

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

int N;
long long A,B,C;
int x[NMax],r[NMax];

void Count(int a[], int b[], long long byte)
{
    long long cnt[260] = {0}, index[260]={0};

    for(long long i=0;i<N;i++)
    {
        long long digit=(a[i]>>(byte*8))&255;
        cnt[digit]++;
    }

    for(long long i=1;i<256;i++)
        index[i]=index[i-1]+cnt[i-1];

    for(long long i=0;i<N;i++)
    {
        long long digit=(a[i]>>(byte*8))&255;
        b[index[digit]++]=a[i];
    }
}

int main()
{
    fin>>N;
    fin>>A>>B>>C;
    x[0]=B%C;
    for(int i=1;i<=N;i++)
        x[i]=(1LL*A*x[i-1]%C+B)%C;

    for(int i=0;i<4;i++)
        if(i%2==0)
            Count(x,r,i);
        else
            Count(r,x,i);

    for(int i=0;i<N;i+=10)
        fout<<x[i]<<" ";

    return 0;
}