Cod sursa(job #2690967)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 26 decembrie 2020 16:22:54
Problema Statistici de ordine Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 1.07 kb
import random
def read_gen(filename):
    with open(filename, 'rt') as fin:
        for line in fin:
            for x in line.split():
                yield int(x)


def find_k_stat(v, start, end, k):
    if start == end:
        return v[start]
    pivot = random.randint(start, end)
    v[pivot], v[end] = v[end], v[pivot]
    # everything < bound is <= than v[pivot]
    bound = start
    for i in range(start, end):
        if v[i] <= v[end]:
            v[bound], v[i] = v[i], v[bound]
            bound += 1
    # put the pivot in the right place
    v[end], v[bound] = v[bound], v[end]
    # k is assumed to be in [start, end]
    if bound == k:
        return v[k]
    elif bound < k:
        return find_k_stat(v, bound + 1, end, k)
    else:
        return find_k_stat(v, start, bound, k)


if __name__ == '__main__':
    it = read_gen(filename='sdo.in')
    n, k = next(it), next(it)
    v = [0] + [next(it) for _ in range(n)]

    with open('sdo.out', 'wt') as fout:
        ans = find_k_stat(v, 1, n, k)
        fout.write('{0}\n'.format(ans))