Cod sursa(job #2309765)

Utilizator st_marianStoica Marian st_marian Data 29 decembrie 2018 19:21:26
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
#define NMAX 10000005
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int N, A, B, C;
int p;
int v[NMAX], out[NMAX];
void counting_sort(int p);
int main()
{
    fin>>N>>A>>B>>C;
    v[1]=B;
    for(int i=2; i<=N; i++)
    {
        v[i]=1LL*(v[i-1]*A+B)%C;
    }
    p=0;
    counting_sort(p);
    p+=8;
    counting_sort(p);
    p+=8;
    counting_sort(p);
    p+=8;
    counting_sort(p);
    for(int i=1; i<=N; i+=10) fout<<v[i]<<' ';
    return 0;
}
void counting_sort(int p)
{
    int poz[256];
    for(int i=0; i<=255; i++)    poz[i]=0;
    for(int i=1; i<=N; i++)
    {
        int x=(v[i]>>p)&255;
        poz[x]++;
    }
    int sumpart=0;
    for(int i=0; i<=255; i++)
    {
        sumpart+=poz[i];
        poz[i]=sumpart;
    }
    for(int i=N; i; i--)
    {
        int x=(v[i]>>p)&255;
        out[poz[x]]=v[i];
        poz[x]--;
    }
    for(int i=1; i<=N; i++) v[i]=out[i];
}