Cod sursa(job #2589123)

Utilizator bigmixerVictor Purice bigmixer Data 25 martie 2020 20:19:51
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax=10000005;
const int mod=1e9+7;

int n,x,y,z,arr[nmax],tz[nmax];

int maximum(){
    int maxi=0;
    for(int i=1;i<=n;i++) maxi=max(maxi,arr[i]);
    int rs=0;
    while(maxi){
        maxi/=10;
        rs++;
    }
    return rs;
}

void counting(int imp){
    int dp[10];
    for(int i=0;i<=9;i++) dp[i]=0;
    for(int i=1;i<=n;i++){
        dp[(arr[i]/imp)%10]++;
    }
    for(int i=1;i<=9;i++) dp[i]+=dp[i-1];
    for(int i=n;i>=1;i--){
        tz[dp[(arr[i]/imp)%10]]=arr[i];
        dp[(arr[i]/imp)%10]--;
    }
    for(int i=1;i<=n;i++) arr[i]=tz[i];
}

void radixsort(int sz){
    int maxi=0;
    for(int i=1;i<=n;i++) maxi=max(maxi,arr[i]);
    for(int curr=1;curr<=maxi;curr*=10){
        counting(curr);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    ifstream cin("radixsort.in");
    ofstream cout("radixsort.out");
    cin >> n >> x >> y >> z;
    arr[1]=y;
    for(int i=2;i<=n;i++){
        int val=(arr[i-1]*x+y)%z;
        arr[i]=val;
    }
    int sz=maximum();
    radixsort(sz);
    for(int i=1;i<=n;i+=10) cout << arr[i] << ' ';
}