Cod sursa(job #3228555)

Utilizator alex_0747Gheorghica Alexandru alex_0747 Data 8 mai 2024 19:17:58
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int v[10000005], n;
vector <int> b[256];

int main()
{
    int i, j, k, A, B, C, mx, lg;
    fin >> n >> A >> B >> C;
    v[1] = B;
    mx = B;
    for (i = 2; i <= n; i++)
    {
        v[i] = (A * v[i - 1] + B) % C;
        mx = max(mx, v[i]);
    }

    for (lg = 0; mx > 0; lg++, mx /= 16)
        ;

    for (i = 0; i < lg; i++)
    {
        for (j = 1; j <= n; j++)
            b[(v[j] >> (i * 8)) & ((1 << 8) - 1)].push_back(v[j]);
        k = 0;
        for (j = 0; j < 256; j++)
        {
            for (int p : b[j])
                v[++k] = p;
            b[j].clear();
        }
    }

    for (i = 1; i <= n; i += 10)
        fout << v[i] << " ";
    return  0;
}