Cod sursa(job #2536822)

Utilizator Constantin.Dragancea Constantin Constantin. Data 2 februarie 2020 18:15:25
Problema Statistici de ordine Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.56 kb
import random
def kth_element(a : list, k : int):
    x = random.choice(a)
    to_left = [y for y in a if y < x]
    to_right = [y for y in a if y > x]
    szl, szr = len(to_left), len(to_right)
    sz = len(a)
    if szl >= k:
        return kth_element(to_left, k)
    if k <= sz - szr:
        return x
    return kth_element(to_right, k - (sz - szr))

f = open('sdo.in', 'r')
n, k = [int(x) for x in f.readline().split()]
lst = [int(x) for x in f.readline().split()]

g = open('sdo.out', 'w')
g.write(str(kth_element(lst, k)))

f.close()
g.close()