Cod sursa(job #2617741)

Utilizator grecuGrecu Cristian grecu Data 22 mai 2020 18:29:47
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.81 kb
/*
from math import log

def convert(k):
    K = []
    for values in k.values():
        for value in values:
            K.append(value)
    return K


def radixsort(l):
    if len(l)==0 or max(l)==0:
        return l
    baza_radix = 255
    curent = 1
    k = {}
    n = (int(log(max(l), baza_radix)) + 1)
    for _ in range(n):
        for i in range(baza_radix):
            k[i] = []
        for i in l:
            k[(i // curent) % baza_radix].append(i)
        l = convert(k)
        curent *= baza_radix
    return l

with open("radixsort.in","r") as f:
    x = f.readline().split()
    n, a, b, c = int(x[0]), int(x[1]), int(x[2]), int(x[3])
l = [b]
for i in range(n-1):
    l.append((a * l[-1] + b)%c)
l = radixsort(l)
with open("radixsort.out",'w') as g:
    for i in range(0,len(l) - 1,10):
        g.write(str(l[i])+" ")


*/



#include <iostream>
#include <fstream>
using namespace std;


ifstream in("radixsort.in");
ofstream out("radixsort.out");
long int n, a, b, c;
int v[10000000];
short int base = 256;

int max(int v[], int n){
    int max = v[0];
    for (int i = 1; i < n; i++)
        if (v[i] > max)
            max = v[i];
    return max;
}
/*
def radixsort(l):
    if len(l)==0 or max(l)==0:
        return l
    baza_radix = 255
    curent = 1
    k = {}
    n = (int(log(max(l), baza_radix)) + 1)
    for _ in range(n):
        for i in range(baza_radix):
            k[i] = []
        for i in l:
            k[(i // curent) % baza_radix].append(i)
        l = convert(k)
        curent *= baza_radix
    return l

with open("radixsort.in","r") as f:
    x = f.readline().split()
    n, a, b, c = int(x[0]), int(x[1]), int(x[2]), int(x[3])
l = [b]
for i in range(n-1):
    l.append((a * l[-1] + b)%c)
l = radixsort(l)
with open("radixsort.out",'w') as g:
    for i in range(0,len(l) - 1,10):
        g.write(str(l[i])+" ")


*/


void radixsort(int v[], int n, short int base = 256){
    int counter[256], aux[10000000];
    if(n != 0 && max(v,n) != 0){
        for(int i = 0; i <= 32; i += 8){
            for(int j = 0; j < 256; j++){
                counter[j] = 0;
            }
            for(int j = 0; j < n; j++){
                counter[(v[j] >> i) & 255] ++;
            }
            for(int j = 1; j < 256; i++){
                counter[i] += counter[i - 1];
            }
            for (int j = n -1; i >= 0; i--){
                aux[--counter[(v[j] >> i) & 255]] = v[i];
            }
            v = aux;
        }


    }
}


int main()
{
    in>>n>>a>>b>>c;
    v[0] = b;
    for(int i = 0; i <= n; i++){
        v[i] = (v[i-1]*a + b) % c;
    }

    radixsort(v,n);
    cout<<n;
    for(int i=0; i < n; i += 10){
        out << v[i] << " ";
        cout << v[i] << " ";
    }
    return 0;
}