Cod sursa(job #1835871)

Utilizator valentin50517Vozian Valentin valentin50517 Data 27 decembrie 2016 15:27:13
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
#define gb(x) ((x>>(8*byte))&(255))
#define NMAX 10000100
using namespace std;

int arr[NMAX],N,a,b,c;

void countsort(int A[],int B[],int byte){
    int count[256],ind[256];
    for(int i = 0;i<256;i++) count[i] = 0;

    for(int i = 0;i<N;i++) count[gb(A[i])]++;

    ind[0] = 0;
    for(int i = 1;i<256;i++) ind[i] = ind[i-1] + count[i-1];

    for(int i = 0;i<N;i++) B[ind[gb(A[i])]++] = A[i];

}

void radixsort(int A[]){

    int* B = new int[N+10];

    for(int i = 0;i<4;i++)
    if(i%2) countsort(B,A,i); else countsort(A,B,i);
}

int main(){
    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> a >> b >> c;
    arr[0] = b%c;
    for(int i = 1;i<N;i++) arr[i] = (1LL * a * arr[i-1] % c + b) % c;

    radixsort(arr);
    for(int i = 0;i<N;i+=10) cout << arr[i] << ' ';
}