Cod sursa(job #2449464)

Utilizator voyagerSachelarie Bogdan voyager Data 19 august 2019 20:13:39
Problema Radix Sort Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.95 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

    first = True
    def countsort(v1, v2, byteNo):
        global first
        if not first:
            for i in range(len(cnt)): cnt[i] = 0
        else:
            first = False
        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)

    print(' '.join(str(v[i]) for i in range(0, N, 10)))