Cod sursa(job #2070915)

Utilizator amaliarebAmalia Rebegea amaliareb Data 20 noiembrie 2017 00:19:51
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int MaxN = 10000005;
int n, v[MaxN], pow10[10];
vector<int> bucket[10];

inline int cifra(int a, int poz)
{
    int c = (a / pow10[poz - 1]) % 10;
    return c;
}

int main()
{
    int a, b, c;
    f >> n >> a >> b >> c;
    pow10[0] = 1;
    for (int i = 1; i <= 9; i++) pow10[i] = 10 * pow10[i - 1];
    v[1] = b;
    ///v[i] = (A * v[i-1] + B) % C
    for (int i = 2; i <= n; i++)
    {
        long long x;
        x = (a * v[i - 1] + b) % c;
        v[i] = (int) x;
    }
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 1; j <= n; j++) bucket[cifra(v[j], i)].push_back(v[j]);
        int n2 = 0;
        for (int i = 0; i <= 9; i++)
        {
            for (int j = 0; j < bucket[i].size(); j++) v[++n2] = bucket[i][j];
            bucket[i].clear();
        }
    }
    for (int i = 1; i <= n; i += 10) g << v[i] << ' ';
    return 0;
}