Cod sursa(job #2537106)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 3 februarie 2020 01:11:48
Problema Statistici de ordine Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.76 kb
def get_pivot(v):
    if len(v) < 5:
        return sorted(v)[len(v) // 2]
    else:
        subv = [v[i : i + 5] for i in range(0, len(v), 5)]
        newv = [sorted(i)[len(i) // 2] for i in subv]
        return get_pivot(newv)

def nth_element(v, k):
    pivot = get_pivot(v)
    small = [i for i in v if i < pivot]
    equal = [i for i in v if i == pivot]
    big = [i for i in v if i > pivot]

    if len(small) >= k:
        return nth_element(small, k)
    k -= len(small)
    if len(equal) >= k:
        return pivot
    k -= len(equal)
    return nth_element(big, k)

fin = open("sdo.in", "r")
fout = open("sdo.out", "w")

n, k = [int(i) for i in fin.readline().split()]
v = [int(i) for i in fin.readline().split()]
print(str(nth_element(v, k)))

fin.close()
fout.close()