Cod sursa(job #1699007)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 5 mai 2016 20:50:24
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int maxn = 10000005;
vector <int> liste[10];
int v[maxn];
int n;
int stop;
void radix(long long p)
{
    if(p >= 10LL * stop)
        return;
    for(int i = 1; i <= n; i++)
        liste[(v[i] / p) % 10].push_back(v[i]);
    int poz = 0;
    for(int i = 0; i < 10; i++)
    {
        for(auto it : liste[i])
            v[++poz] = it;
        liste[i].clear();
    }
    radix(p * 10);
}

int main()
{
    int a, b, c;
    in >> n >> a >> b >> c;
    v[1] = b;
    int mx = 0;
    for(int i = 2; i <= n; i++)
    {
        v[i] = (1LL * v[i-1] * a + b) % c;
        mx = max(mx, v[i]);
    }
    stop = 1;
    while(stop * 10 <= mx)
        stop = stop * 10;
    radix(1);
    for(int i = 1; i <= n; i += 10)
        out << v[i] << " ";
    out << "\n";
    return 0;
}