Cod sursa(job #2975954)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 7 februarie 2023 21:34:02
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("popcnt")

using namespace std;

ifstream fin  ("radixsort.in");
ofstream fout ("radixsort.out");

const int MAX_N = 10'000'000;
int n, a, b, c;
int v[MAX_N + 5], w[MAX_N + 5];

int cif[10];
static inline void radixsort(){
    int maxx = 0;
    for(int i=1; i<=n; i++)
        maxx = max(maxx, v[i]);

    int zlim = 1;
    while(maxx != 0){
        maxx /= 10;
        if(maxx != 0)
            zlim *= 10;
    }

    for(int z10=1; z10<=zlim; z10*=10){

        for(int i=0; i<=9; i++)
            cif[i] = 0;

        for(int i=1; i<=n; i++)
            cif[ v[i] / z10 % 10 ]++;

        for(int i=1; i<=9; i++)
            cif[i] += cif[i-1];

        for(int i=n; i>=1; i--){
            w[ cif[v[i] / z10 % 10] ] = v[i];
            cif[v[i] / z10 % 10]--;
        }

        for(int i=1; i<=n; i++)
            v[i] = w[i];
    }
}

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>a>>b>>c;
    v[1] = b;
    for(int i=2; i<=n; i++)
        v[i] = ((long long)v[i-1] * a + b) % c;

    radixsort();

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