Cod sursa(job #2702676)

Utilizator DragosC1Dragos DragosC1 Data 5 februarie 2021 14:16:26
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
using namespace std;
 
int n;
int a[10000001];
 
#define get_byte(x) ((x >> (byte * 8)) & 255)
 
void countsort(int x[], int y[], int byte) {
    int i;
    int counter[256] = {0};
    int index[256];
    
    for(i = 0; i < n; i ++)
        ++counter[get_byte(x[i])];
    
    index[0] = 0;
    
    for(i = 1; i < 256; i ++)
        index[i] = index[i-1] + counter[i-1];
    
    for(i = 0; i < n; i++)
        y[index[get_byte(x[i])]++] = x[i];
}
void radixsort() {
    int i;
    int *temp = new int[n];
    for (i = 0; i < 4; i ++) {
        if(i % 2 == 0)
            countsort(a, temp, i);
        else
            countsort(temp, a, i);
    }
}
 
int main() {
    int i, x, y, z;
 
    ifstream f("radixsort.in");
    f >> n >> x >> y >> z;
    f.close();
 
    a[0] = y;
    for (i = 1; i < n; i++)
        a[i] = (1LL * x * a[i - 1] + 1LL * y) % z;
 
    radixsort();
 
    ofstream g("radixsort.out");
    for (i = 0; i < n; i += 10)
        g << a[i] << ' ';
    g.close();
 
    return 0;
}