Cod sursa(job #3291666)

Utilizator octavurlurleteanu alexandru octavian octavurl Data 5 aprilie 2025 11:34:06
Problema Radix Sort Scor 30
Compilator cpp-32 Status done
Runda cex_9 Marime 1.18 kb
#include <bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define pb(x) push_back(x)
#define ins(x) insert(x)
#define mp(x,y) make_pair(x,y)
#define fast_ios ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ifstream fin ( "radixsort.in" ) ;
ofstream fout ( "radixsort.out");
void radix_sort ( vector<int>&v , ll exp )
{
vector<int>output(v.size(),0);
vector<int>co ( 10 , 0 );
for ( int i =0 ; i < v.size() ; ++ i )
    ++co[(v[i]/exp) % 10 ];
for ( int i =1 ; i < 10 ; ++ i )
    co[i] += co[i-1];
for ( int i = v.size() - 1; i >= 0  ;-- i )
{
    int digit = ( v[i] / exp ) % 10;
    output[co[digit]-1] = v[i];
    --co[digit];
}
v=output;
}
int main()
{
    fast_ios
    ll n;
    int a , b , c;
    fin >> n >> a >> b >> c;
    vector<int>v(n+1,0);
    v[1]=b;
    int max1 = 0 ;
    for ( int i = 2 ; i <= n ; ++ i )
           {
            v[i]=(( a * 1LL * v[i-1] + b ) % c );
            max1 = max ( max1 , v[i]);
           }

    for ( ll exp = 1 ; max1 / exp > 0 ; exp *= 10 )
        radix_sort(v,exp);
    for ( int i = 1 ; i <= n ; i += 10 )
        fout << v [i] << ' ' ;
    return 0;

}