Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**18 + 1
lo = -1 * 10**18 -1

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

            


Fixed submission:


from bisect import bisect

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        # i=0のときと組み合わせが被らないようにjは1から
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            # A[i]が負なので、A[i] * A[j]は単調減少
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            # あるiについて、A[i] * A[j~N-1] <= mid を満たすペアの数を足す
            cnt_under_mid += (N - j)

            # この時点で積がmid以下になるペアの数がK個以上あれば、そのmidについてそれ以上調べる必要はない
            if cnt_under_mid >= K:
                return True

            # この時点で積がmidのペアの個数がK未満かつ、それ以上mid以下にできる組み合わせがない場合、探索を打ち切る
            if j >= N:
                break

        return False

    # midが0以上の場合、

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 # A[l]が負のindexで一番右にあるやつ
        for l in range(cnt_negative):
            a = A[l]
            # A[l] * A[r]はrを左に寄せてくるにつれて大きくなる（負 x 負で,右側の負の徐々に絶対値が大きくなるから）
            while a * A[r] <= mid:
                r -= 1
                # lについて、いずれのrをペアにとってもmidを上回らないなら、負の要素についての探索を打ち切る
                if r <= -1:
                    break
            cnt_over_mid += r+1 # 例えばidxでj=2になった時に積がmidを上回るなら、j=0,1,2の三つとの積でmidを超える、みたいな
            # 同じインデックスでペアを作る場合、重複を取り除く
            if r >= l: cnt_duplicate += 1
            # iを右に動かすにつれて、ｊを左に動かさないとmidを超える積ができなくなる（iを右にすると絶対値が小さくなるので、jのほうは絶対値を大きくする必要がある）
            # jをもう動かすことができなくなったら、A[i]が負の場合に、それ以上midを上回るペアを作れないので探索を打ち切る
            if r <= -1:
                break
        
        # Aの要素について、負以外の場合
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        # 今度は右から見ていって、対象をlとして、lより右側にある物とペアになればmidを超える、みたいな
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                # ペアを作って積がmidを超えるまで、lを右にずらしていく
                l += 1
                # これ以上lを右にずらせない場合打ち切り
                if l >= N:
                    break
            # あるrについて、lより右にあるものとペアを作るとmidを超えるので、その個数を足す
            cnt_over_mid += N-l
            # rのペアにrを選んでいる場合は取り除く
            if l <= r:
                cnt_duplicate += 1

            # それ以上lを右にずらせない場合は探索を打ち切る
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


ok = 10**18 + 1
ng = -1 * 10**18 - 1

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**18 + 1
lo = -1 * 10**18 -1

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

            


Fixed submission:


from bisect import bisect

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        # i=0のときと組み合わせが被らないようにjは1から
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            # A[i]が負なので、A[i] * A[j]は単調減少
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            # あるiについて、A[i] * A[j~N-1] <= mid を満たすペアの数を足す
            cnt_under_mid += (N - j)

            # この時点で積がmid以下になるペアの数がK個以上あれば、そのmidについてそれ以上調べる必要はない
            if cnt_under_mid >= K:
                return True

            # この時点で積がmidのペアの個数がK未満かつ、それ以上mid以下にできる組み合わせがない場合、探索を打ち切る
            if j >= N:
                break

        return False

    # midが0以上の場合、

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 # A[l]が負のindexで一番右にあるやつ
        for l in range(cnt_negative):
            a = A[l]
            # A[l] * A[r]はrを左に寄せてくるにつれて大きくなる（負 x 負で,右側の負の徐々に絶対値が大きくなるから）
            while a * A[r] <= mid:
                r -= 1
                # lについて、いずれのrをペアにとってもmidを上回らないなら、負の要素についての探索を打ち切る
                if r <= -1:
                    break
            cnt_over_mid += r+1 # 例えばidxでj=2になった時に積がmidを上回るなら、j=0,1,2の三つとの積でmidを超える、みたいな
            # 同じインデックスでペアを作る場合、重複を取り除く
            if r >= l: cnt_duplicate += 1
            # iを右に動かすにつれて、ｊを左に動かさないとmidを超える積ができなくなる（iを右にすると絶対値が小さくなるので、jのほうは絶対値を大きくする必要がある）
            # jをもう動かすことができなくなったら、A[i]が負の場合に、それ以上midを上回るペアを作れないので探索を打ち切る
            if r <= -1:
                break
        
        # Aの要素について、負以外の場合
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        # 今度は右から見ていって、対象をlとして、lより右側にある物とペアになればmidを超える、みたいな
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                # ペアを作って積がmidを超えるまで、lを右にずらしていく
                l += 1
                # これ以上lを右にずらせない場合打ち切り
                if l >= N:
                    break
            # あるrについて、lより右にあるものとペアを作るとmidを超えるので、その個数を足す
            cnt_over_mid += N-l
            # rのペアにrを選んでいる場合は取り除く
            if l <= r:
                cnt_duplicate += 1

            # それ以上lを右にずらせない場合は探索を打ち切る
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


ok = 10**18 + 1
ng = -1 * 10**18 - 1

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**20
lo = -1 * 10**20

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

            

Fixed submission:


from bisect import bisect

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        # i=0のときと組み合わせが被らないようにjは1から
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            # A[i]が負なので、A[i] * A[j]は単調減少
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            # あるiについて、A[i] * A[j~N-1] <= mid を満たすペアの数を足す
            cnt_under_mid += (N - j)

            # この時点で積がmid以下になるペアの数がK個以上あれば、そのmidについてそれ以上調べる必要はない
            if cnt_under_mid >= K:
                return True

            # この時点で積がmidのペアの個数がK未満かつ、それ以上mid以下にできる組み合わせがない場合、探索を打ち切る
            if j >= N:
                break

        return False

    # midが0以上の場合、

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 # A[l]が負のindexで一番右にあるやつ
        for l in range(cnt_negative):
            a = A[l]
            # A[l] * A[r]はrを左に寄せてくるにつれて大きくなる（負 x 負で,右側の負の徐々に絶対値が大きくなるから）
            while a * A[r] <= mid:
                r -= 1
                # lについて、いずれのrをペアにとってもmidを上回らないなら、負の要素についての探索を打ち切る
                if r <= -1:
                    break
            cnt_over_mid += r+1 # 例えばidxでj=2になった時に積がmidを上回るなら、j=0,1,2の三つとの積でmidを超える、みたいな
            # 同じインデックスでペアを作る場合、重複を取り除く
            if r >= l: cnt_duplicate += 1
            # iを右に動かすにつれて、ｊを左に動かさないとmidを超える積ができなくなる（iを右にすると絶対値が小さくなるので、jのほうは絶対値を大きくする必要がある）
            # jをもう動かすことができなくなったら、A[i]が負の場合に、それ以上midを上回るペアを作れないので探索を打ち切る
            if r <= -1:
                break
        
        # Aの要素について、負以外の場合
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        # 今度は右から見ていって、対象をlとして、lより右側にある物とペアになればmidを超える、みたいな
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                # ペアを作って積がmidを超えるまで、lを右にずらしていく
                l += 1
                # これ以上lを右にずらせない場合打ち切り
                if l >= N:
                    break
            # あるrについて、lより右にあるものとペアを作るとmidを超えるので、その個数を足す
            cnt_over_mid += N-l
            # rのペアにrを選んでいる場合は取り除く
            if l <= r:
                cnt_duplicate += 1

            # それ以上lを右にずらせない場合は探索を打ち切る
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


ok = 10**18 + 1
ng = -1 * 10**18 - 1

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Buggy python submission (verdict: Time Limit Exceeded):

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


"""
最終的に、hiは条件を満たす最小の値となり、loは条件を満たさない最大の値になる
"""
hi = 10**20
lo = -1 * 10**20

while hi - lo > 1:
    mid = (hi + lo) // 2
    cnt_under_mid = 0
    cnt_duplicate = 0

    """
    小さいものからK番目の値が欲しいので、
    Aの要素それぞれについて、積を取ってmid以下になるものの個数を合算して、
    ・K個以上の場合、midの値がまだ大きいのでhiをmidまで下げる（例えばmid=10**1000　以下の個数を数えるとすると、全てがこれ以下になるのでhi大きすぎるから下げる、みたいな）
    ・K個未満の場合、midの値が小さいので、loをmidまであげる（mid=-1*10**1000だとすると、どれもこの値以下にならないので、現行のlo~midまでは条件を満たさない）
    """
    # 
    for a in A:
        # a > 0であれば、a * A[m] >= mid を満たす最小のmについて、A[m~N-1]がaと積を取ってmid以上になる（積が単調増加になるから）
        if a > 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                
                if a * A[m] <= mid:
                    l = m
                else:
                    r = m
            # a * A[0:r-1]までのr個は、積をとってもmid未満
            cnt_under_mid += r
        # a < 0であれば、a * A[m] >= mid を満たす最大のmについて、A[0~m]がaと積を取ってmid以上になる（積が単調減少になるから）
        elif a < 0:
            r  = N
            l = -1
            while r - l > 1:
                m = (r + l) // 2
                if a * A[m] <= mid:
                    # rより後ろにあるものと積をとってもmid未満
                    r = m
                else:
                    l = m
            # a * A[r~N-1]のN-r個は、積をとってもmid未満
            cnt_under_mid += N - r 
        # a = 0 の場合、何と積をとっても0になるので、mid以下の個数を探すので、mid>=0であれば全てのAについて条件を満たす
        elif mid >= 0:
            cnt_under_mid += N

        # ↑で求めたものはA[i] * A[i]もペアとして扱ってるので、それがmid以下になる場合は取り除く
        if a * a <= mid:
            cnt_duplicate += 1

    cnt = (cnt_under_mid - cnt_duplicate) // 2

    #print("---", hi,lo,mid)
    # Kを超える場合は、midが大きすぎる（XXX以下の個数を求めてるので、hiをおろしてくる）
    if cnt >= K:
        hi = mid
    
    else:
        lo = mid




print(hi)

            

Fixed submission:


from bisect import bisect

N,K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

cnt_positive = N - bisect(A, 0)
cnt_zero = A.count(0)
cnt_negative = N - cnt_positive - cnt_zero


def is_ok(mid):
    
    if mid < 0:
        cnt_under_mid = 0
        # i=0のときと組み合わせが被らないようにjは1から
        j = 1
        for i in range(cnt_negative):
            a = A[i]
            # A[i]が負なので、A[i] * A[j]は単調減少
            while a * A[j] > mid:
                j += 1
                if j >= N:
                    break
            # あるiについて、A[i] * A[j~N-1] <= mid を満たすペアの数を足す
            cnt_under_mid += (N - j)

            # この時点で積がmid以下になるペアの数がK個以上あれば、そのmidについてそれ以上調べる必要はない
            if cnt_under_mid >= K:
                return True

            # この時点で積がmidのペアの個数がK未満かつ、それ以上mid以下にできる組み合わせがない場合、探索を打ち切る
            if j >= N:
                break

        return False

    # midが0以上の場合、

    else:
        """
        こちらではmidより大きくなる個数を全ペアの個数から引いて考える
        """
        cnt_over_mid = 0
        cnt_duplicate = 0
        r = cnt_negative-1 # A[l]が負のindexで一番右にあるやつ
        for l in range(cnt_negative):
            a = A[l]
            # A[l] * A[r]はrを左に寄せてくるにつれて大きくなる（負 x 負で,右側の負の徐々に絶対値が大きくなるから）
            while a * A[r] <= mid:
                r -= 1
                # lについて、いずれのrをペアにとってもmidを上回らないなら、負の要素についての探索を打ち切る
                if r <= -1:
                    break
            cnt_over_mid += r+1 # 例えばidxでj=2になった時に積がmidを上回るなら、j=0,1,2の三つとの積でmidを超える、みたいな
            # 同じインデックスでペアを作る場合、重複を取り除く
            if r >= l: cnt_duplicate += 1
            # iを右に動かすにつれて、ｊを左に動かさないとmidを超える積ができなくなる（iを右にすると絶対値が小さくなるので、jのほうは絶対値を大きくする必要がある）
            # jをもう動かすことができなくなったら、A[i]が負の場合に、それ以上midを上回るペアを作れないので探索を打ち切る
            if r <= -1:
                break
        
        # Aの要素について、負以外の場合
        cnt_not_positive = cnt_negative + cnt_zero
        l = cnt_not_positive
        # 今度は右から見ていって、対象をlとして、lより右側にある物とペアになればmidを超える、みたいな
        for r in range(N-1, cnt_not_positive-1, -1):
            a = A[r]
            while a * A[l] <= mid:
                # ペアを作って積がmidを超えるまで、lを右にずらしていく
                l += 1
                # これ以上lを右にずらせない場合打ち切り
                if l >= N:
                    break
            # あるrについて、lより右にあるものとペアを作るとmidを超えるので、その個数を足す
            cnt_over_mid += N-l
            # rのペアにrを選んでいる場合は取り除く
            if l <= r:
                cnt_duplicate += 1

            # それ以上lを右にずらせない場合は探索を打ち切る
            if l >= N:
                break
        
        cnt_under_mid = (N*(N-1) // 2) - ((cnt_over_mid - cnt_duplicate) // 2)
        return cnt_under_mid >= K


ok = 10**18 + 1
ng = -1 * 10**18 - 1

while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)