Cod sursa(job #2845399)

Utilizator francescom_481francesco martinut francescom_481 Data 7 februarie 2022 19:33:28
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb

#include <bits/stdc++.h>

using namespace std;

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

#define N 10000005
#define MOD 2048
int v[2][N], a, b, c, n, nr, maxim;
int cnt[2050];

void reord(int putere, int aux)
{
    memset(cnt,0,sizeof(cnt));
    for(int i = 0 ; i < n ; i++)
    {
        cnt[(v[aux][i]/putere)%2048]++;
    }
    for(int i = 1 ; i < 2048 ; i++)
    {
        cnt[i] += cnt[i-1];
    }
    for(int i = n-1 ; i >= 0 ; i--)
    {
        v[1-aux][--cnt[(v[aux][i]/putere)%2048]] = v[aux][i];
    }
}
void radix()
{
    for(int i = 1; maxim/i ; i *= 2048, nr++)
    {
        reord(i,nr%2);
    }
}

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