Cod sursa(job #2900222)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 10 mai 2022 15:30:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

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

//ifstream f("D:/Proiecte/Clion/Projects/hashuri.in");
//ofstream g("D:/Proiecte/Clion/Projects/hashuri.out");

unsigned int n, a, b, c, v[10000003], aux[10000003];

const int TOTAL_BYTES = sizeof(v[0]);
const int max_number_of_digits = 8;

inline unsigned int get_byte(unsigned int x, int k_byte){
    return (x >> (k_byte * 8)) & ((1 << 8) - 1);
}

void RadixSort(unsigned int v[], int s, int d){

    for(int k_byte = 0; k_byte < 4; ++k_byte){
        int counter[256] = {0}, index[256];

        for(int i = s; i <= d; ++i)
            ++counter[get_byte(v[i], k_byte)];

        index[0] = 0;
        for(int i = 1; i < 256; ++i)
            index[i] = index[i - 1] + counter[i - 1];

        for(int i = s; i <= d; ++i)
            aux[index[get_byte(v[i], k_byte)]++] = v[i];

        for(int i = s; i <= d; ++i)
            v[i] = aux[i];
    }

}

int main(){

    f >> n >> a >> b >> c;

    v[0] = b;

    for(int i = 1; i < n; ++i)
        v[i] = (1LL * a * v[i - 1] % c + b) % c;

    RadixSort(v, 0, n - 1);

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

    f.close();
    g.close();

    return 0;
}