Cod sursa(job #2669610)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 7 noiembrie 2020 12:32:08
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>

using namespace std;

const int NMAX = 10000000;
const int BYTE = (1 << 8) - 1;

ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int N, A, B, C;
int v[NMAX + 5], v2[NMAX + 5], aux[BYTE + 5];

int main()
{
    cin >> N >> A >> B >> C;

    v[1] = B;
    for(int i = 2; i <= N; i++)
        v[i] = (1LL * A * v[i - 1] + B) % C;

    for(int i = 0; i < 4; i++)
    {

        for(int j = 0; j <= BYTE; j++)
            aux[j] = 0;

        for(int j = 1; j <= N; j++)
            aux[(v[j] >> (8 * i)) & BYTE]++;

        for(int j = 1; j <= BYTE; j++)
            aux[j] += aux[j - 1];

        for(int j = N; j >= 1; j--)
            v2[aux[(v[j] >> (8 * i)) & BYTE]--] = v[j];

        for(int j = 1; j <= N; j++)
            v[j] = v2[j];
    }

    for(int i = 1; i <= N; i += 10)
        cout << v[i] << ' ';

    return 0;
}