Cod sursa(job #2244797)

Utilizator AnDrEeA1915Monea Andreea AnDrEeA1915 Data 23 septembrie 2018 18:21:39
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 10000005;
const int bits = 8, size = 1<<bits , mask = size-1;
int N, A, B, C;
int v[nmax], aux[nmax];

int getMask(int x, int off)
{
    return (x >> off) & mask;
}
void countSort(int src[],int dest[],int off)
{
    int cnt[size],indx[size];
    memset(cnt,0,sizeof cnt);
    for(int i = 0;i < N; ++i)
        ++cnt[getMask(src[i],off)];
    indx[0]=0;
    for(int i = 1; i < size; ++i)
        indx[i] = cnt[i-1] + indx[i-1];
    for(int i = 0;i < N; ++i)
        dest[indx[getMask(src[i],off)]++] = src[i];
}
void radixSort()
{
    for (int i = 0; i * bits < 32; ++i)
        if (i&1)
            countSort(aux,v,i*bits);
        else
            countSort(v,aux,i*bits);
}

int main(){
    ifstream fin("radixsort.in");
    fin >> N >> A >> B >> C;
    v[0] = B;
    for(int i = 1; i < N; ++i)
        v[i] = (1LL*A*v[i-1]+B)%C;
    radixSort();
    ofstream fout("radixsort.out");
    for(int i = 0;i<N; i += 10)
        fout << v[i] <<" ";
    fout << "\n";
    return 0;
}