Cod sursa(job #2669614)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 7 noiembrie 2020 12:35:01
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>

using namespace std;

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

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

int N, A, B, C;
int v[NMAX + 5], v2[NMAX + 5], cnt[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++)
            cnt[j] = 0;

        for(int j = 1; j <= N; j++)
            cnt[(v[j] >> (i * BUCKET)) & (BYTE - 1)]++;

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

        for(int j = N; j >= 1; j--) ///stable sort
            v2[cnt[(v[j] >> (i * BUCKET)) & (BYTE - 1)]--] = 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;
}