Cod sursa(job #3351913)

Utilizator unomMirel Costel unom Data 22 aprilie 2026 11:46:35
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>

using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");
int v[10000005];
int temp[10000005];
int frec[15];
int start[15];
int n, a, b, c;
int MAX_DIGIT = 10;

void radix_sort()
{
    int put = 1;
    while(1)
    {
        int sorted = 1;
        for(int i = 2; i<=n; i++)
        {
            if(v[i - 1] > v[i])
            {
                sorted = 0;
                break;
            }
        }

        if(sorted == 1)
        {
            break;
        }

        for(int i = 1; i<=n; i++)
        {
            int d = (v[i] / put) % MAX_DIGIT;
            frec[d]++;
        }

        int poz = 1;
        for(int i = 0; i<MAX_DIGIT; i++)
        {
            start[i] = poz;
            poz += frec[i];
        }

        for(int i = 1; i<=n; i++)
        {
            int d = (v[i] / put) % MAX_DIGIT;
            temp[start[d]] = v[i];
            start[d]++;
        }

        for(int i = 0; i<MAX_DIGIT; i++)
        {
            frec[i] = 0;
        }
        swap(v, temp);
        put *= MAX_DIGIT;
    }
}

int main()
{
    in>>n>>a>>b>>c;
    v[1] = b;
    for(int i = 2; i<=n; i++)
    {
        v[i] = (1LL*a * v[i-1] % c + b) % c;
    }

    radix_sort();

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