Cod sursa(job #2537101)

Utilizator Constantin.Dragancea Constantin Constantin. Data 3 februarie 2020 00:36:36
Problema Statistici de ordine Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.59 kb
import random


def nth_element(v: list, k: int):
    if len(v) == 1:
        return v[0]

    a = random.choice(v)
    small = [i for i in v if i < a]
    big = [i for i in v if i > a]
    eq = [i for i in v if i == a]

    if len(small) >= k:
        return nth_element(small, k)
    else:
        k -= len(small)
    if len(eq) >= k:
        return a
    return nth_element(big, k - len(eq))


fin = open("sdo.in", "r")

n, k = [int(x) for x in fin.readline().split()]
v = [int(x) for x in fin.readline().split()]

fout = open("sdo.out", "w")
fout.write(str(nth_element(v, k)))