Cod sursa(job #2465714)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 30 septembrie 2019 18:42:33
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <cstring>

using namespace std;

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

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

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

int main()
{
    fin >> 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++)
    {
        memset(ct, 0, sizeof(ct));

        for(int j = 1; j <= N; j++)
        {
            int val = (v[j] >> (i << 3)) & (BYTE - 1);
            ct[val]++;
        }

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

        for(int j = N; j >= 1; j--)
        {
            int val = (v[j] >> (i << 3)) & (BYTE - 1);

            aux[ct[val]] = v[j];
            ct[val]--;
        }

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

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

    return 0;
}