Cod sursa(job #3129151)

Utilizator RK13Barbu Eduard RK13 Data 12 mai 2023 21:31:33
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;


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

int n,a,b,c;
int v[10000005],aux[10000005],counter[260];

int get_byte(int x, int byte)
{
    return ((x>>(byte*8))&((1<<8)-1)); //x shiftat la dreapta cu bucket*8 biti, pastrandu-se 8 biti, pornind de la 8*bucket
}

void countingsort(int a[], int b[], int exp)
{int i;
    memset(counter, 0, sizeof(counter));
    for (i=1;i<=n;i++)
        counter[get_byte(a[i],exp)]++;

    for (i=1;i<=256;i++)
        counter[i]+=counter[i-1];

    for (i=n;i>=1;i--)
        b[counter[get_byte(a[i],exp)]--]=a[i];
}

void radixsort()
{
    for (int i=0;i<4;i++) //i e bucket pt 8 biti, 4 bucketuri deci in total 32 de biti
    if (i%2==0)
        countingsort(v,aux,i);
    else
        countingsort(aux,v,i);
}

int main()
{
    int i;
    f>>n>>a>>b>>c;
    v[1]=b;
    for (i=2;i<=n;i++)
        v[i]=(1LL*a*v[i-1]+b)%c;
    radixsort();
    for (i=1;i<=n;i+=10)
        g<<v[i]<<' ';
}