Cod sursa(job #2482000)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 27 octombrie 2019 17:51:23
Problema Statistici de ordine Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 1.16 kb
#!/bin/python3

import sys
import os
import re


def generate_list(A, B, x):
    n = len(A)
    m = len(B)
    L = []

    for i in range(min(n, m - x)):
        for j in range(i + x, m):
            L.append(A[i] * B[j])

    return L

def kthSmallest(arr, left, right, k):

    while k > 0 and k <= right - left + 1:
        pos = partition(arr, left, right)

        if pos - left == k - 1:
            return arr[pos]
        elif pos - left > k - 1:
            right = pos - 1
        else:
            k -= pos - left + 1
            left = pos + 1

    return -sys.maxsize

def partition(arr, left, right):

    elem = arr[right]
    i = left
    for j in range(left, right):
        if arr[j] <= elem:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[right] = arr[right], arr[i]

    return i

if __name__ == "__main__":

    fptr_in = open("sdo.in", 'r')
    fptr_out = open("sdo.out", 'w')

    n, k = list(map(int, fptr_in.readline().rstrip().split()))
    arr = list(map(int, fptr_in.readline().rstrip().split()))

    result = kthSmallest(arr, 0, n - 1, k)
    fptr_out.write(str(result) + '\n')

    fptr_in.close()
    fptr_out.close()