Cod sursa(job #2581441)

Utilizator Mirela_MagdalenaCatrina Mirela Mirela_Magdalena Data 15 martie 2020 12:11:22
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#define MASK 0xFF
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

int n, a, b, c, maxnr;
vector<int> v, aux;
int frc[10];
void formv()
{
    aux.resize(n+5);
    v.push_back(0);
    v.push_back(b);
    for(int i = 2; i <= n; ++i)
    {
        int val = (1LL*v[i-1]*a + b)%c;
        if(val > maxnr)
            maxnr = val;
        v.push_back(val);
    }
}

void afis(int step)
{
    for(int i = 1; i <= n; i += step)
        printf("%d ", v[i]);
}

void countSort(int cif)
{
    for(int i = 0; i < 10; ++i)
        frc[i] = 0;

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

    for(int i = 1; i < 10; ++i)
        frc[i] += frc[i-1];

    for(int i = n; i >= 1; --i)
    {
        aux[ frc[(v[i]/cif)%10]] = v[i];
        frc[(v[i]/cif)%10]--;
    }
    swap(aux, v);
}
//   1   2   3   4   5   6   7   8
// 170  45  75  90 802  24   2  66
// 170  90 802   2   4  45  75  66



void radix()
{
    for(int cif = 1; maxnr / cif > 0; cif *= 10)
        countSort(cif);
}

void read()
{
    scanf("%d %d %d %d", &n, &a, &b, &c);
    formv();
}

void readaux()
{
    int x;
    scanf("%d ", &n);
    aux.resize(n+5);
    v.push_back(0);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d ", &x);
        if(x > maxnr)
            maxnr = x;
        v.push_back(x);
    }
}
int main()
{
    freopen("radixsort.in", "r", stdin);
    freopen("radixsort.out", "w", stdout);
    read();
    radix();
    afis(10);
    return 0;
}