Cod sursa(job #2737139)

Utilizator niculaandreiNicula Andrei Bogdan niculaandrei Data 4 aprilie 2021 14:33:49
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
#define Byte(x) ((x >> (16 * byte)) & 255)

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

const int N_MAX = 1e7 + 5;

int N, A, B, C;
int v[N_MAX];

void CountingSort(int byte)
{
    vector < int > aux[(1 << 17)];
    for (int i = 1; i <= N; i++) {
        aux[Byte(v[i])].push_back(v[i]);
    }

    int pos = 1;
    for (int mask = 0; mask < (1 << 17); mask++) {
        for (int i = 0; i < aux[mask].size(); i++) {
            v[pos++] = aux[mask][i];
        }
    }
}

void RadixSort()
{
    for (int byte = 0; byte < 2; byte++) {
        CountingSort(byte);
    }
}

int main()
{
    fin >> N >> A >> B >> C;
    v[1] = B;
    for (int i = 2; i <= N; i++) {
        v[i] = (1LL * v[i - 1] * A + B) % C;
    }
    RadixSort();
    for (int i = 1; i <= N; i += 10) {
        fout << v[i] << " ";
    }
    return 0;
}