Cod sursa(job #2844093)

Utilizator francescom_481francesco martinut francescom_481 Data 3 februarie 2022 19:03:42
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
#define cin fin
#define cout fout

#define N 2005
int v[N], arr[N], a, b, c, n, maxim;

void reord(int putere)
{
    int cnt[1005] = {0};
    for(int i = 0 ; i < n ; i++)
    {
        cnt[(v[i]/putere)%1000]++;
    }
    for(int i = 1 ; i < 1000 ; i++)
    {
        cnt[i] += cnt[i-1];
    }
    for(int i = n-1 ; i >= 0 ; i--)
    {
        arr[--cnt[(v[i]/putere)%1000]] = v[i];
    }
    for(int i = 0 ; i <= n ; i++)
    {
        v[i] = arr[i];
    }
}
void radix()
{
    for(int i = 1 ; maxim/i ; i *= 1000)
    {
        reord(i);
    }
}

int main()
{
    cin >> n >> a >> b >> c;
    v[0] = b;
    maxim = b;
    for(int i = 1 ; i < n ; i++)
    {
        v[i] = (1ll*v[i-1]*a+b)%c;
        maxim = max(maxim, v[i]);
    }
    radix();
    for(int i = 0 ; i < n ; i += 10)
    {
        cout << v[i] << " ";
    }
	return 0;
}