Cod sursa(job #2945038)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 23 noiembrie 2022 13:02:42
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>

using namespace std;

#define Nmax 10000000
long long v[Nmax];

void radixSort(int left, int right, int bitNumber)
{
    if(left > right || bitNumber <= -1)
    {
        return;
    }

    int i, j;

    for(i = left, j = left; i <= right; i++)
    {
        if((v[i] & (1 << bitNumber)) == 0)
        {
            swap(v[i], v[j]);
            j++;
        }
    }

    radixSort(left, j - 1, bitNumber - 1);
    radixSort(j, right, bitNumber - 1);
}

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

    int n, i, a, b, c;

    fin >> n >> a >> b >> c;

    v[0] = b;
    for(i = 1; i < n; i++)
    {
        v[i] = ((long long)a * v[i - 1] + b) % c;
    }

    radixSort(0, n - 1, 63);

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