Cod sursa(job #2191060)

Utilizator Narvik13Razvan Roatis Narvik13 Data 1 aprilie 2018 15:17:01
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
///RADIX SORT PE CIFRE
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 10000002

using namespace std;

ifstream f("radixsort.in");
ofstream o("radixsort.out");

int n,a,b,c;
int v[NMAX];
queue <int> q[10];

void input()
{
    f >> n >> a >> b >> c;
    v[1] = b;
    for(int i = 2; i <= n; ++i)
            v[i] = (1LL * a * v[i-1] + b) % c;
}

void radix_sort()
{
    int imp = 1;
    for(int i = 1; i <= 10; ++i)
    {
        for(int j = 1; j <= n; ++j)
            q[(v[j]/imp)%10].push(v[j]);

        int p = 0;
        for(int i = 0; i <= 9; ++i)
            while(not q[i].empty())
            {
                v[++p] = q[i].front();
                q[i].pop();
            }


        imp *= 10;
    }
}

void output()
{
    for(int i = 1; i <= n; i += 10)
        o << v[i] << ' ';
}

int main()
{
    input();
    radix_sort();
    output();
    return 0;
}