Problem:


Score: 400 points

Problem Statement

We have N integers A_1, A_2, ..., A_N.

There are \frac{N(N-1)}{2} ways to choose two of them and form a pair. If we compute the product of each of those pairs and sort the results in ascending order, what will be the K-th number in that list?

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq K \leq \frac{N(N-1)}{2}

-10^9 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 3
3 3 -4 -2

Sample Output 1

-6

There are six ways to form a pair. The products of those pairs are 9, -12, -6, -12, -6, 8.

Sorting those numbers in ascending order, we have -12, -12, -6, -6, 8, 9. The third number in this list is -6.

Sample Input 2

10 40
5 4 3 2 -1 0 0 0 0 0

Sample Output 2

6

Sample Input 3

30 413
-170202098 -268409015 537203564 983211703 21608710 -443999067 -937727165 -97596546 -372334013 398994917 -972141167 798607104 -949068442 -959948616 37909651 0 886627544 -20098238 0 -948955241 0 -214720580 277222296 -18897162 834475626 0 -425610555 110117526 663621752 0

Sample Output 3

448283280358331064



Sample input:
4 3
3 3 -4 -2


Sample output:
-6

Submission status: Runtime Error

Solution code:
d

Submission status: Runtime Error

Solution code:
n,order = map(int, input().split())
nums = [int(str) for str in input().split()]
maxn = int(n * (n-1) /2)
result = list(range(maxn))
bangou = 0

for x in range(n-1):
  for y in range(n):
    if y > x:
      result[bangou] = int( nums[x] * nums[y] )
      bangou += 1
result.sort()
print(result[order-1])

Submission status: Runtime Error

Solution code:
n,k=input().split(" ")
arr=input().split(" ")

list=[]
for i in range(len(arr)-1):
    for j in range(i+1,len(arr)):
        val=int(int(arr[i])*int(arr[j]))
        list.append(val)

print(sorted(list)[int(k)])

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
aa = map(int, input().split())

p = []
for i in range(N-1):
  for j in range(i+1, N):
    p.append(i*j)

print(p.sorted[K])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
def func(n, k, A):
    A.sort()
    A_ = [0]*(n*(n-1)//2)
    c = 0
    for i in range(n-1):
        for j in range(i+1, n):
            A_[c] = A[i]*A[j]
            c += 1
    A_.sort()
    print(A_[k-1])

if n==2:
    print(A[0]*A[1])
else:
    func(n, k, A)

Submission status: Runtime Error

Solution code:
import numpy as np

n, k = map(int,input().split())

a = np.asarray(list(map(int, input().split())), dtype=np.int64)

values = np.zeros(int(((n*(n-1))/2)), dtype=np.int64)
number = 0

for i in range(n):
    for j in range(i+1,n):
        values[number] = a[i] * a[j]
        number += 1

sorted_values = np.sort(values)

print(int(sorted_values[k-1]))

Submission status: Runtime Error

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

import numpy as np
A = np.array(A).reshape(-1, 1)
M = (A * A.reshape(1, -1)).ravel()
M.sort()
print(M[K-1])

Submission status: Runtime Error

Solution code:
# N個の整数
# K番目は何？
N, K = map(int, input().split())

# リスト
A = list(map(int, input().split()))

result = []
for i in range(0,N-1):
    for l in range(i+1,N):
        result.append(A[i]*A[l])

result.sort()
print(result[K])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))

s = []

for i in range(0, n - 1):
    for j in range(i + 1, n):
        s.append(a[i] * a[j])
sx = sorted(s)
#print(sx)
print(sx[k])

Submission status: Runtime Error

Solution code:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    table = [0] * (n*(n-1)//2+1)
    c = 0
    for i in range(n):
        for j in range(i+1, n):
            table[c] = a[i]*a[j]
            c += 1
    table = sorted(table)
    print(table[k])


main()

Submission status: Runtime Error

Solution code:
N=int(input())
di = dict()
for i in range(N):
    s = input()
    if s in di:
        di[s] += 1
    else:
        di[s] = 0

maxlist = [kv for kv in di.items() if kv[1] == max(di.values())]
for d in sorted(maxlist):
    print(d[0])

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n,k = inpm()
    a = inpl()
    minus,zero,plus = 0,0,0
    a.sort()
    x,y,z = [],[],[]
    for i in range(n):
        if a[i] < 0:
            minus += 1
            x.append(a[i])
        elif a[i] == 0:
            zero += 1
            y.append(a[i])
        else:
            plus += 1
            z.append(a[i])
    if k <= minus*plus:
        ans = []
        for i in range(minus):
            for j in range(plus):
                ans.append(x[i]*z[minus-j-1])
                if (i+1)*(j+1)>k+1:
                    break
            if (i+1)*(j+1)>k:
                break
        ans.sort()
        print(ans[k-1])
    elif k <= minus*plus + zero*(minus+plus):
        print(0)
    else:
        k -= minus*plus + zero*(minus+plus) + zero*(zero-1)//2
        ans = []
        for i in range(minus-1):
            for j in range(i+1,minus):
                ans.append(x[minus-1-i]*x[minus-1-j])
                if (i+1)*(j+1) > k+1:
                    break
            if (i+1)*(j+1) > k+1:
                break
        for i in range(plus-1):
            for j in range(i+1,plus):
                ans.append(z[i]*z[j])
                if (i+1)*(j+1) > k+1:
                    break
            if (i+1)*(j+1) > k+1:
                break
        ans.sort()
        print(ans[k-1])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
A_ = [0]*(n*(n-1)//2)
c = 0
for i in range(n-1):
    for j in range(i+1, n):
        A_[c] = A[i]*A[j]
        c += 1
A_.sort()
print(A_[k-1])

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations, combinations, combinations_with_replacement, product

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

ans = [0] * (N * (N - 1) // 2)
for i, p in enumerate(combinations(A, 2)):
    ans[i] = p[0] * p[1]

print(sorted(ans)[K - 1])

Submission status: Runtime Error

Solution code:
N = int(input())
ans = {}
for i in range(N):
	cood = input()
	if  cood not in ans:
		ans[cood] = 1
	else:
		ans[cood] += 1
max_k_list = [kv[0] for kv in ans.items() if kv[1] == max(ans.values())]
max_k_list.sort()
for i in range(len(max_k_list)):
	print(max_k_list[i])

Submission status: Runtime Error

Solution code:
import itertools
import heapq

N,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
A=sorted(A,reverse=True)[:K]

q=[]
heapq.heapify(q)
for i in itertools.combinations(A,2):
    heapq.heappush(q,i[0]*i[1])


for i in range(K):
    a=heapq.heappop(q)

print(a)