Cod sursa(job #2900224)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 10 mai 2022 15:33:02
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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)
            if(k_byte % 2 == 0)
                ++counter[get_byte(v[i], k_byte)];
            else
                ++counter[get_byte(aux[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)
            if(k_byte % 2 == 0)
                aux[index[get_byte(v[i], k_byte)]++] = v[i];
            else
                v[index[get_byte(aux[i], k_byte)]++] = 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;
}