Cod sursa(job #2775785)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 17 septembrie 2021 09:51:36
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#define NMAX 10000005

using namespace std;

/**********************************/
/// INPUT / OUTPUT

ifstream f("radixsort.in");
ofstream g("radixsort.out");
/**********************************/
/// GLOBAL DECLARATIONS

int N, A, B, C;
int arr[NMAX];
int temp[NMAX];
int bucket[269];
/**********************************/
int main()
{
    f >> N >> A >> B >> C;
    arr[1] = B;
    for (int i = 2 ; i <= N ; ++ i)
        arr[i] = (1LL * A * arr[i - 1] + B) % C;
    for (int k = 0 ; k < 32 ; k += 8)
    {
        for (int i = 0 ; i < 256 ; ++ i)
            bucket[i] = 0;
        
        for (int i = 1 ; i <= N ; ++ i)
            bucket[(arr[i] >> k) & 255] ++;
        
        for (int i = 1 ; i < 256 ; ++ i)
            bucket[i] += bucket[i - 1];

        for (int i = N ; i >= 1 ; -- i)
        {
            temp[bucket[(arr[i] >> k) & 255] --] = arr[i];
        }

        for (int i = 1 ; i <= N ; ++ i)
            arr[i] = temp[i];
    }
    for (int i = 1 ; i <= N ; i += 10)
        g << arr[i] << " ";    
    return 0;
}