Cod sursa(job #2297359)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 5 decembrie 2018 19:06:55
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define Nmax 10000005
#define ByteMax 32
#define get_byte(x) ((x>>(byte*8))&255)

using namespace std;

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

int v[Nmax],t[Nmax],n;

void count_sort(int *A, int *B, int byte)
{
    int cnt[256],idx[256];
    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<n;i++)
        ++cnt[get_byte(A[i])];

    idx[0]=0;
    for(int i=1;i<=255;i++)
        idx[i]=idx[i-1]+cnt[i-1];

    for(int i=0;i<n;i++)
        B[idx[get_byte(A[i])]++]=A[i];
}

int main()
{
    int a,b,c;
    f>>n>>a>>b>>c;
    v[0]=b;
    for(int i=1;i<n;i++)
        v[i]=((a*v[i-1])%c+b)%c;

    for(int i=0;i<ByteMax;i++)
        if(i&1)
            count_sort(t,v,i);
        else count_sort(v,t,i);

    for(int i=0;i<n;i+=10)
        g<<v[i]<<' ';

    return 0;
}