Cod sursa(job #2449466)

Utilizator voyagerSachelarie Bogdan voyager Data 19 august 2019 20:18:27
Problema Radix Sort Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.86 kb
#!/usr/bin/env python3

import sys
sys.stdout = open('radixsort.out', 'w')

with open('radixsort.in', 'r') as f:
    N, A, B, C = tuple(map(int, f.readline().split()))

    v = [B] * N
    for i in range(1, N):
        v[i] = (A * v[i - 1] + B) % C
    aux = [0] * len(v)
    cnt = [0] * 0x100

    def byte(x, byteNo):
        return (x >> (byteNo << 3)) & 0xFF

    def countsort(v1, v2, byteNo):
        for i in range(len(cnt)): cnt[i] = 0
        for x in v1: cnt[byte(x, byteNo)] += 1
        for i in range(1, len(cnt)): cnt[i] += cnt[i - 1]

        for x in reversed(v1):
            b = byte(x, byteNo)
            v2[cnt[b] - 1] = x
            cnt[b] -= 1

    for byteNo in range(4):
        if byteNo & 1:
            countsort(aux, v, byteNo)
        else:
            countsort(v, aux, byteNo)

    for i in range(0, N, 10):
        print(v[i], end=' ')
    print()