Pagini recente » Cod sursa (job #2451242) | Cod sursa (job #2451248) | Cod sursa (job #2699559) | Cod sursa (job #1623121) | Cod sursa (job #2690967)
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))