Cod sursa(job #1972839)

Utilizator GeorginskyGeorge Georginsky Data 23 aprilie 2017 20:19:54
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <deque>
#define pb push_back
#define pf pop_front
using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
deque<int> bucket[10], v;
int n, a, b, c, d;
int main(){
    in>>n>>a>>b>>c;
    v.pb(b);
    int x, y, b2=b, d2;
    while(b2>0)b2/=10,d++;
    for(int i=1; i<n; i++){
        x=(a*v[i-1]+b)%c;
        v.pb(x);
        d2=0;
        while(x>0)x/=10,d2++;
        d=max(d, d2);
    }
    x=10, y=1;
    for(int i=1; i<=d; i++){
        while(!v.empty()){
            bucket[(v[0]%x)/y].pb(v[0]);
            v.pf();
        }
        for(int j=0; j<=9; j++){
            while(!bucket[j].empty()){
                v.pb(bucket[j][0]);
                bucket[j].pf();
            }
        }
        x*=10, y*=10;
    }
    for(int i=1; i<=n; i+=10)out<<v[i-1]<<" ";
    return 0;
}