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: Wrong Answer

Solution code:
k=int(input().split()[1])
source = input().split()

target = []
print(len(source))

for j in range(0,len(source)):
    num=source[j]
    for i in range(j+1, len(source)):
    #for i in range(0, len(sorted_source)):
        target.append(int(num)*int(source[i]))

#sorted_target=list(reversed(sorted(target)))
print(target)
sorted_target=sorted(target)
print(sorted_target)
print(sorted_target[k-1])

Submission status: Wrong Answer

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

ans = []
for i in range(N-1):
    ans += map(lambda x: x*A[i], A[i+1:])
    print(ans)
ans.sort()
print(ans[K-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from bisect import bisect_left
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

def count(m):
    res = 0
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
        if a**2<=m:
            res -= 1
    res //= 2
    return res

def count1(m):
    res = 0
    cand = -10**19
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
            if j!= 0:
                cand = max(cand,a*A[j-1])
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
            if j != N:
                cand = max(cand,a*A[j])
        if a**2<=m:
            res -= 1
    res //= 2
    return res,cand


l = -10**18
r = 10**18
m = (l+r)/2
for i in range(60):
    k = count(m)
    if k < K:
        l = m
    else:
        r = m
    m = (l+r)/2
k,ans = count1(r)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

def val_times(v):
    return v[0] * v[1]

N, K = map(int, input().split(' '))
A = list(map(float, input().split(' ')))
# print(sorted([val_times(v) for v in itertools.combinations(A, 2)]))
v = sorted([val_times(v) for v in itertools.combinations(A, 2)])[K-1]
print('{:.0f}'.format(v))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = []
X = 0
for i in range(K):
  for j in range(i+1,N):
    X = A[i]*A[j]
    B.append(X)
    if len(B)==K:
      break
B_ = sorted(B)
ans = B_[K-1]
print(ans)

Submission status: Wrong Answer

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

A = list(map(int,input().split()))

memo =[]

for i in range(N):
	for j in range(i+1,N):
		memo.append(A[i]*A[j])
memo.sort()
print(memo)
print(memo[K-1])

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect

def query_number_less_than_or_equal_to_k(A, B, cnt_zero, k):
    na = len(A)
    nb = len(B)
    ans = 0
    if 0 <= k:
        ans += cnt_zero * (na + nb)
    ans += cnt_zero * (cnt_zero - 1) // 2
    for i in range(na):
        first = i + 1
        last = bisect.bisect_right(A, k // A[i], lo = i + 1)
        ans += last - first
    for i in range(nb):
        first = i + 1
        last = bisect.bisect_right(B, k // B[i], lo = i + 1)
        ans += last - first
    for a in A:
        first = bisect.bisect_left(B, (-k+a-1) // a)
        last = nb
        ans += last - first
    return ans

def solve(A, m):
    n = len(A)
    B = []
    C = []
    cnt_zero = 0
    for a in A:
        if a == 0:
            cnt_zero += 1
        elif a > 0:
            B.append(a)
        elif a < 0:
            C.append(-a)
    B.sort()
    C.sort()
    '''
    print('A: %s' % str(A))
    print('m: %d' % m)
    print('B: %s' % str(B))
    print('C: %s' % str(C))
    for i in range(-10, 0, 1):
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, i)
        print('i: %d, val: %d' % (i, val))
    return -1
    '''
    left = -10 ** 18
    right = 10 ** 18
    while right - left > 1:
        mid = (left + right) // 2
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, mid)
        #print('left: %d, right: %d, mid: %d, val: %d' % (left, right, mid, val))
        if val >= m:
            right = mid
        else:
            left = mid
    return right

def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(A, m)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

n, k = map(int, raw_input().split())
seq = map(int, raw_input().split())

memo = dict()
res = list()

for n1, n2 in list(itertools.combinations(seq, 2)):
    pair = tuple(sorted([n1, n2]))
    try:
        if memo[pair]:
            res.append(memo[pair])
        res.append(n1 * n2)
    except KeyError:
        r = n1 * n2
        memo[pair] = r
        res.append(r)

print sorted(res)[k-1]

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
AA =[0,]
for i in range(N-1):
    for j in range(i+1,N):
        AA.append(A[i]*A[j])
del AA[0]
print(sorted(AA))
print(sorted(AA)[K-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
lst = np.array([int(x) for x in input().split()])
newLst = np.array([])

for i in range(n-1):
    for j in range(i+1, n):
        newLst = np.append(newLst, [lst[i]*lst[j]])

newLst = sorted(newLst)
print(int(newLst[k-1]))

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from bisect import bisect_left
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

def count(m):
    res = 0
    cand = -10**19
    for i in range(N):
        a = A[i]
        if a==0:
            if m>=0:
                res += N
        elif a>0:
            r = m/a
            j = bisect(A,r)
            res += j
            if j!= 0:
                cand = max(cand,a*A[j-1])
        else:
            r = m/a
            j = bisect_left(A,r)
            res += N-j
            if j != N:
                cand = max(cand,a*A[j])
        if a**2<=m:
            res -= 1
    res //= 2
    return res,cand


l = -10**18
r = 10**18
m = (l+r)/2
for i in range(60):
    k,cand = count(m)
    if k < K:
        l = m
    else:
        r = m
    m = (l+r)/2
k,ans = count(r)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,K=map(int,input().split())
A=list(map(int,input().split()))
c = itertools.combinations(A, 2)
k=[]
for v in c:
    print(v)
    s=v[0]*v[1]
    k.append(s)
k.sort()
print(k[K-1])

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int, input().split()))
a=sorted(a)
numlist=[]
for i in range(len(a)-1):
  numlist.append(a[i]*a[i+1])
def cheak(ans):
  if len(ans)>=k:
    tmp=ans[-1]
    ans=sorted(ans)
    ind=ans.index(tmp)
    if ind >= k:
      return ans[k]
  return None
ans=[]
for i in range(len(a)-1):
  if a[i]<=0:
    for j in range(len(a)-1,-1,-1):
      if i==j:break
      ans.append(a[i]*a[j])
      r=cheak(ans)
      if r!=None:
        print(r)
        exit(0)
  else:
    for j in range(i,len(a)):
      ans.append(a[i]*a[j])
      r=cheak(ans)
      if r!=None:
        print(r)
        exit(0)

Submission status: Wrong Answer

Solution code:
from itertools import product,combinations
N,K = map(int,input().split())
A1 = list(map(int,input().split()))
dicta = {}
for i in A1:
    if i not in dicta:
        dicta[i] = 1
    else:
        dicta[i]+=1
A = list(dicta.keys())
ap = [i for i in A if i > 0]
am = [i for i in A if i < 0]
lenp = sum(dicta[i] for i in ap)
lenm = sum(dicta[i] for i in am)
azero = N -lenp - lenm
zerocomb = azero*(N-azero) + azero*(azero-1)//2
minus = lenp*lenm
if minus >= K:
    ans = []
    for a,b in product(ap,am):
        num = a*b
        count = dicta[a]*dicta[b]
        ans.append((num,count))
    ans.sort()
    count = 0
    for n,c in ans:
        count += c
        if count >= K:
            print(n)
            break
elif K <= minus+zerocomb:
    print(0)
else:
    ans = []
    for a,b in combinations(ap,2):
        num = a*b
        count = dicta[a]*dicta[b]
        ans.append((num,count))
    for a,b in combinations(am,2):
        num = a*b
        count = dicta[a]*dicta[b]
        ans.append((num,count))
    ans.sort()
    count = 0
    for n,c in ans:
        count += c
        if count >= K-minus-zerocomb:
            print(n)
            break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
products = []
for i in range(N):
  for j in range(i+1, N):
    if len(products) == 0:
      products.append(A[i]*A[j])
    for k in range(len(products)):
      if A[i]*A[j] >= max(products):
        products.append(A[i]*A[j])
        break
      elif A[i]*A[j] <= products[k]:
        products.insert(k, A[i]*A[j])
        break
print(products[K-1])

Submission status: Wrong Answer

Solution code:
def main():
  import itertools
  N,K =map(int, input().split())
  A=list(map(int, input().split()))
  
  cc = list(itertools.combinations(A,2))
  B=[0]*len(cc)
  print(B)
  for i,v in enumerate(cc):
    B[i] = v[0]*v[1]
  c= sorted(B)
  print(c[K-1])

main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
from bisect import bisect_left


N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]


def solveAm(A, N, K):
    A = sorted(A, reverse=True)
    cumsum = [N-1]
    for i in range(2, N): cumsum.append(cumsum[i-2]+N-i)

    y = bisect_left(cumsum, K)
    x = N-1-cumsum[y]+K
    return A[y]*A[x]

def solveAp(A, N, K):
    A = sorted(A)
    cumsum = [N-1]
    for i in range(2, N): cumsum.append(cumsum[i-2]+N-i)

    y = bisect_left(cumsum, K)
    x = N-1-cumsum[y]+K
    return A[y]*A[x]

if all([i <= 0 for i in A]):
    print(solveAm(A, N, K))
elif all([i >= 0 for i in A]):
    print(solveAp(A, N, K))

# else:
#     neg = 0
#     for i in A:
#         if i<0: neg+=1
#     m = neg*(N-neg)
#     if m>=K:

Submission status: Wrong Answer

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

d=[]
for i in range(N-1):
  for j in range(i+1,N):
    d.append(A[i]*A[j])
s=sorted(d)

print(s)
print(s[K-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
from bisect import bisect_left as bl
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=10**18,-10**18-1
while l-r>1:
    t=(l+r)//2
    p=0
    for i in range(n):
        if a[i]<0:
            c=bl(a,t/a[i])
            p+=n-c
            if i>c:
                p-=1
        elif a[i]==0:
            if t>=0:
                p+=n-1
        else:
            c=br(a,t/a[i])
            p+=br(a,t/a[i])
            if i<c:
                p-=1
    p//=2
    if p>=k:
        l=t
    else:
        r=t
g=-float("INF")
for i in range(n):
    if a[i]<0:
        c=bl(a,l/a[i])
        if c==i:
            c+=1
        if c<n:
            g=max(g,a[c]*a[i])
    elif a[i]==0:
        g=max(g,0)
    else:
        c=br(a,l/a[i])-1
        if c==i:
            c-=1
        if c>0:
            g=max(g,a[c]*a[i])
print(g)

Submission status: Wrong Answer

Solution code:
N,K  = map(int,input().split())
nums = list(map(int,input().split()))
# preprocess
#
neg_nums= []
pos_nums = []
zeros = 0
pos =  0
neg = 0
for num in nums:
    if num < 0:
        neg_nums.append(num)
        neg += 1
    elif num > 0:
        pos_nums.append(num)
        pos += 1
    else:
        zeros += 1



LIM = N *  (N - 1) //2

complex_nums = sorted(nums,key = lambda x:abs(x))
cot = [0] * N
zero_limits = zeros * (zeros -1 ) //2+  zeros * (pos + neg)
if  1 <= K <= neg * pos: #負の値の領域
    complex_nums.reverse()
    for i,num in enumerate(complex_nums):
        if num < 0:
            cot[i] += pos
            neg -= 1
        elif num >0:
            cot[i] += neg
            pos -= 1
    acc = 0
    for i,temp in enumerate(cot):
        if acc+ temp >= K:
            key = complex_nums[i]
            nokori = K - acc
            for one_more in complex_nums[i + 1:]:
                if key * one_more < 0:
                    nokori -= 1
                    if nokori == 0:
                        print(key * one_more)
                        exit(0)
        else:
            acc += temp
elif  neg * pos < K <=  neg * pos  + zero_limits:# 0の領域
    print(0)
else: # 正の値の領域
    # complex_nums = sorted(nums, key=lambda x: -abs(x))
    K -=(neg * pos + zero_limits)
    for i,num in enumerate(complex_nums):
        if num < 0 and neg > 0:
            neg -= 1
            cot[i] += neg
        elif num >0 and pos > 0:
            pos -= 1
            cot[i] += pos
    acc = 0
    for i,temp in enumerate(cot):
        if acc+ temp >= K:
            key = complex_nums[i]
            nokori = K - acc
            for one_more in complex_nums[i + 1:]:
                if key * one_more > 0:
                    nokori -= 1
                    if nokori == 0:
                        print(key * one_more)
                        exit(0)
        else:
            acc += temp

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(i) for i in input().split()]

if k < n * (n-1) // 4: #kが小さい
    a.sort()
    arr = []
    for i in range(n-1):
        for j in range(i+1, n):
            b = a[i] * a[j]
            if len(arr) < k-1:
                arr.append(b)
            elif len(arr) == k-1:
                arr.append(b)
                arr.sort()
            elif b >= arr[k-1] and a[i] >= 0: #a[j] > a[i] > 0
                break
            elif b < arr[k-1]:
                del arr[k-1]
                arr.append(b)
                arr.sort()
    print(arr[k-1])

else: #kが大きい
    k = n * (n - 1) // 2 - k + 1
    a.sort(reverse=True)
    arr = []
    for i in range(n-1): #a[i] >= a[j]
        for j in range(i+1, n):
            b = a[i] * a[j]
            if len(arr) < k-1:
                arr.append(b)
            elif len(arr) == k-1:
                arr.append(b)
                arr.sort(reverse=True)
            elif b <= arr[k-1] and a[i] <= 0: #0 > a[i] >= a[j]
                break
            elif b > arr[k-1]:
                del arr[k-1]
                arr.append(b)
                arr.sort(reverse=True)
    print(arr[k-1])

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
mib = -10 ** 18 * 2
mab = 10**18*2
c = 0
o = 0
while mib != mab:
    b = (mib + mab) // 2

    maa = -10**18*2
    co = 0
    for i in a:
        mi = 0
        ma = n - 1
        if i >= 0:
            if i * a[0] > b:
                continue
            while mi != ma:
                mm = (mi + ma) // 2 + 1
                if i * a[mm] <= b:
                    mi = mm
                else:
                    ma = mm - 1
            co += mi + 1
            maa = max(maa, i * a[mi])
            if i * i <= b:
                co -= 1
        else:
            if i * a[-1] > b:
                continue
            while mi != ma:
                mm = (mi + ma) // 2
                if i * a[mm] <= b:
                    ma = mm
                else:
                    mi = mm + 1
            maa = max(maa, i * a[mi])
            co += n - mi
            if i * i <= b:
                co -= 1
    if co // 2 == k:
        break
    if co//2 >= k:
        mab = b
    else:
        mib = b + 1
    o += 1

maa = -10**18*2
co = 0
for i in a:
    mi = 0
    ma = n - 1
    if i >= 0:
        if i * a[0] > mib:
            continue
        while mi != ma:
            mm = (mi + ma) // 2 + 1
            if i * a[mm] <= mib:
                mi = mm
            else:
                ma = mm - 1
        co += mi + 1
        maa = max(maa, i * a[mi])
        if i * i <= mib:
            co -= 1
    else:
        if i * a[-1] > mib:
            continue
        while mi != ma:
            mm = (mi + ma) // 2
            if i * a[mm] <= mib:
                ma = mm
            else:
                mi = mm + 1
        maa = max(maa, i * a[mi])
        co += n - mi
        if i * i <= mib:
            co -= 1
print(maa)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
lis = list(map(int, input().split()))
import itertools
import numpy as np
com = list(itertools.combinations(lis, 2))
newcom = np.empty((len(com), 2))
newcom[:] = com
newlis = list(map(int, np.prod(newcom, axis = 1)))
newlis.sort()
print(newlis[k - 1])

Submission status: Wrong Answer

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

s = sorted(a)
ss = s[:k+1]
l = []
for i in range(len(ss)):
    for j in range(len(ss)):
        if (i > j):
            l.append(ss[i] * ss[j])

print(sorted(l)[k - 1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,K = inpl()
aa = sorted(inpl())

l = bisect.bisect_left(aa, 0)
r = bisect.bisect_right(aa, 0)

aa_m = aa[:l]
aa_0 = aa[l:r]
aa_p = aa[r:]
N_m = len(aa_m)
N_0 = len(aa_0)
N_p = len(aa_p)
zeros = N_m * N_p + N_0 * (N_m+N_p) + (N_0)*(N_0-1)//2

# x 以下をカウント
def solve(x):
    cnt = 0
    if x == 0:
        return zeros
    elif x > 0:
        cnt += zeros
        for i,a in enumerate(aa_m):
            r = bisect.bisect_right(aa_m, x//a)
            cnt += N_m-max(i+1,r)
        for i,a in enumerate(aa_p):
            r = bisect.bisect_right(aa_p,x//a)
            cnt += max(0,r-(i+1))
        return cnt
    elif x < 0:
        for i,a in enumerate(aa_m):
            r = N_p-bisect.bisect_left(aa_p,-(-x//a))
            cnt += r
    return cnt


NG = -(10**20)
OK = 10**20

while OK-NG > 1:
    mid = (OK+NG)//2
    if solve(mid) >= K:
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
b=[]
for j in range(n):
  for l in range(n):
    c=a[j]*a[l]
    b.append(c)
print(b[k])

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = list(map(int, input().split()))
M = [i for i in A if i < 0]
m = len(M)
Z = [i for i in A if i == 0]
z = len(Z)
P = [i for i in A if i > 0]
p = len(P)
if (K > m*p) and (K <= m*p + m + p):
  print(0)

Submission status: Wrong Answer

Solution code:
import itertools

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

num = 0

while (num*(num-1))/2 < k:
  num += 1

l = []

a = list(map(int, input().split()))
a.sort

a = a[0:(num+1)]

for i in itertools.combinations(a, 2):
  c, d = i
  l.append(c*d)

l.sort()

print(l[k-1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N,K = inpl()
aa = sorted(inpl())

l = bisect.bisect_left(aa, 0)
r = bisect.bisect_right(aa, 0)

aa_m = aa[:l]
aa_0 = aa[l:r]
aa_p = aa[r:]

print(aa_m)
print(aa_0)
print(aa_p)
N_m = len(aa_m)
N_0 = len(aa_0)
N_p = len(aa_p)
zeros = N_m * N_p + N_0 * (N_m+N_p) + (N_0)*(N_0-1)//2

# x 以下をカウント
def solve(x):
    cnt = 0
    if x == 0:
        return zeros
    elif x > 0:
        cnt += zeros
        for i,a in enumerate(aa_m):
            r = bisect.bisect_right(aa_m, x//a)
            cnt += N_m-max(i+1,r)
        for i,a in enumerate(aa_p):
            r = bisect.bisect_right(aa_p,x//a)
            cnt += max(0,r-(i+1))
        return cnt
    elif x < 0:
        for i,a in enumerate(aa_m):
            r = N_p-bisect.bisect_left(aa_p,x//a)
            cnt += r
    return cnt


NG = -(10**20)
OK = 10**20

while OK-NG > 1:
    mid = (OK+NG)//2
    if solve(mid) >= K:
        OK = mid
    else:
        NG = mid

print(OK)

Submission status: Wrong Answer

Solution code:
import itertools

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

c = itertools.combinations(temp_list, 2)
num_list = sorted(c, key=lambda x: x[0]*x[1])
print(num_list)

output_list = list(num_list[k-1])
print(output_list[0] * output_list[1])

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [int(x) for x in input().split()]
a.sort()
ans = []

count = -1
for idx in range(0,n-1):
    for idx2 in range(idx+1,n):
        ans.append(a[idx]*a[idx2])
        count += 1
        if count == k:
            ans.sort()
            print(ans[k-1])
            exit()

Submission status: Wrong Answer

Solution code:
import heapq

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

a_list = list(map(int, input().split()))

multiples = []

for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        else:
            multiples.append(a_list[i]*a_list[j])
            #heapq.heappush(multiples, a_list[i]*a_list[j])
 
multiples.sort()
#ans = 0        
#for i in range(k):
#    ans = heapq.heappop(multiples)
    
#print(ans)
multiples[k-1]

Submission status: Wrong Answer

Solution code:
import sys
import math
import bisect

def query_number_less_than_or_equal_to_k(A, B, cnt_zero, k):
    na = len(A)
    nb = len(B)
    '''
    print('A: ' + str(A))
    print('B: ' + str(B))
    print('cnt_zero: %d' % cnt_zero)
    '''
    ans = 0
    if 0 <= k:
        ans += cnt_zero * (na + nb)
    ans += cnt_zero * (cnt_zero - 1) // 2
    for i in range(na):
        first = i + 1
        last = bisect.bisect_right(A, k // A[i], lo = i + 1)
        ans += last - first
    for i in range(nb):
        first = i + 1
        last = bisect.bisect_right(B, k // B[i], lo = i + 1)
        ans += last - first
    for a in A:
        first = bisect.bisect_left(B, -k // a)
        last = nb
        ans += last - first
    return ans

def solve(A, m):
    n = len(A)
    B = []
    C = []
    cnt_zero = 0
    for a in A:
        if a == 0:
            cnt_zero += 1
        elif a > 0:
            B.append(a)
        elif a < 0:
            C.append(-a)
    B.sort()
    C.sort()
    left = -10 ** 19
    right = 10 ** 19
    while right - left > 1:
        mid = (left + right) // 2
        #print('left: %d, right: %d, mid: %d' % (left, right, mid))
        val = query_number_less_than_or_equal_to_k(B, C, cnt_zero, mid)
        if val >= m:
            right = mid
        else:
            left = mid
    return right

def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    ans = solve(A, m)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br, bisect_left as bl

n, k = map(int, raw_input().strip().split())
a = map(int, raw_input().strip().split())

pos = []
neg = []

for num in a:
    if num <= 0: neg.append(num)
    else: pos.append(num)

pos.sort()
neg.sort()

blocks = []
runner = []
for i in xrange(len(neg)):
    blocks.append(len(pos))
    runner.append(neg[i])

if k <= len(neg) * len(pos):
    sz = len(blocks)
    pre = [0] * (sz + 1)

    for i in xrange(1, sz + 1):
        pre[i] = pre[i - 1] + blocks[i - 1]

    idx = bl(pre, k)
    if pre[idx] == k:
        print runner[idx - 1] * pos[-1]
    else:
        diff = k - pre[idx - 1]
        print runner[idx - 1] * pos[diff - 1]

    exit()

k -= (len(neg) * len(pos))

for i in xrange(len(neg)): neg[i] = -neg[i]
neg.sort()

# binary search
lo, hi = 1, 10 ** 18 + 1
while lo < hi:
    mid = (lo + hi) / 2

    # if check(mid)
    # hi = mid
    # else
    # lo = mid + 1

    cur = 0
    for i in xrange(1, len(pos)):
        if pos[i] > mid: break
        y = mid / pos[i]
        cnt = br(pos, y)
        cnt = min(cnt, i)
        cur += cnt

    for i in xrange(1, len(neg)):
        if abs(neg[i]) > mid:
            break
        if neg[i] == 0:
            cur += i
            continue
        
        y = mid / abs(neg[i])
        cnt = br(neg, y)
        cnt = min(cnt, i)
        cur += cnt

    if cur >= k: hi = mid
    else: lo = mid + 1

print lo

Submission status: Wrong Answer

Solution code:
import bisect

def check(N, A, x):
    # count: p*q <= x
    C = 0
    for i in range(N):
        if A[i] == 0:
            if x >= 0:
                add = N - 1
            else:
                add = 0
        elif A[i] < 0:
            add = N - bisect.bisect_left(A, x / A[i])
            if A[i] * A[i] <= x:
                add -= 1
        else:
            add = bisect.bisect_right(A, x / A[i])
            if A[i] * A[i] <= x:
                add -= 1
        C += add
    return C // 2

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    lo = int(-1e20)
    hi = int(1e20)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        # print('mid =', mid)
        C = check(N, A, mid)
        # print('C =', C)
        if C >= K:
            hi = mid
        else:
            lo = mid
    print(hi)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import itertools

firstLineRawInput = input().split()
secondLineRawInput = input().split()

number = int(firstLineRawInput[0])
smaller = int(firstLineRawInput[1])

sekiList = []

kumiawaseList = list(itertools.combinations(secondLineRawInput,2))
print(kumiawaseList)

for n in range(len(kumiawaseList)):
    sekiList.append(int(kumiawaseList[n][0]) * int(kumiawaseList[n][1]))

sortedListF = sorted(sekiList, reverse = False)

print (sortedListF[smaller-1])

Submission status: Wrong Answer

Solution code:
import bisect


def solve(mid):
    # midより小さい通り数を求める
    cnt = 0
    if mid > 0:
        # 正と正の組み合わせ
        for i, num in enumerate(plus):
            tmp = -((-mid) // num)
            ind = bisect.bisect_left(plus, tmp, lo=i+1)
            cnt += ind - (i + 1)

        # 負と負の組み合わせ
        for i, num in enumerate(minus_plus):
            tmp = -((-mid) // num)
            ind = bisect.bisect_left(minus_plus, tmp, lo=i+1)
            cnt += ind - (i + 1)

    if mid >= 0:
        # 正と負の組み合わせ
        cnt += len(minus_plus) * len(plus)

    if mid < 0:
        # 正と負の組み合わせ
        for i, num in enumerate(plus):
            tmp = (-mid) // num
            ind = bisect.bisect_right(minus_plus, tmp)
            cnt += len(minus_plus) - ind
    #print(cnt)

    
    if mid >= 0:
        cnt += cnt_0

    if cnt < k:
        return True
    else:
        return False


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

plus = []
minus_minus = []
minus_plus = []
zero = []
for i in range(n):
    if a[i] > 0:
        plus.append(a[i])
    elif a[i] < 0:
        minus_plus.append(-a[i])
    else:
        zero.append(0)
plus = sorted(plus)
minus_plus = sorted(minus_plus)


cnt_0 = (len(plus) + len(minus_plus)) * len(zero)
cnt_0 += len(zero) * (len(zero) - 1) // 2
    
ng = 10**20
ok = -10**20

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

Submission status: Wrong Answer

Solution code:
import itertools

N, K = [int(num) for num in input().split(' ')]
As = [int(num) for num in input().split(' ')]

AA = sorted([a*b for a,b in itertools.combinations(As, r=2)])

print(AA)
print(AA[K-1])

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A_neg = []
A_zero = []
A_pos = []
for i in A:
    if i < 0:
        A_neg.append(i)
    elif i == 0:
        A_zero.append(i)
    else:
        A_pos.append(i)
num_neg_pro = len(A_neg) * len(A_pos)
num_zero_pro = len(A_zero) * (len(A_zero) - 1) // 2 + len(A_zero) * (n - len(A_zero))
if k <= num_neg_pro:
    # the smallest number consists of the smallest negative times the largest positive
    A_neg = sorted(A_neg)
    A_pos = sorted(A_pos, reverse = True)
    # each row is a negative, each col is a pos
    row_num = (k-1) // len(A_pos)
    col_num = (k-1) % len(A_pos)
    print(A_neg[row_num] * A_pos[col_num])
elif k <= num_zero_pro + num_neg_pro:
    print(0)
else:
    # either multiply pos with pos or neg with neg
    A_neg = sorted(A_neg, reverse = True)
    A_pos = sorted(A_pos)
    k -= (num_zero_pro + num_neg_pro)
    counter = 0
    ans = []
    A_neg_len = len(A_neg)
    A_pos_len = len(A_pos)
    for i in range(A_neg_len):
        for j in range(i+1, A_neg_len):
            ans.append(A_neg[i]*A_neg[j])
    for i in range(A_pos_len):
        for j in range(i+1, A_pos_len):
            ans.append(A_pos[i]*A_pos[j])
    print(sorted(ans)[k-1])

Submission status: Wrong Answer

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

al = list(map(int,input().split()))
al = sorted(al)
lb = -10**18
ub = 10**18
import bisect

while True:
    if ub == lb:
        print(ub)
        exit()
    target = (ub+lb) // 2
    tmp = 0
    for a in al:
        if a * a <= target:
            tmp -= 1
        if a == 0:
            if target >= 0:
                tmp += n
        elif a < 0:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += n - idx
        else:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += idx
    tmp = tmp // 2
    if tmp >= K:
        ub = target
    else:
        lb = target + 1

Submission status: Wrong Answer

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

al = list(map(int,input().split()))
al = sorted(al)
lb = -10**18
ub = 10**18
import bisect
def ceil(a, b):
   return a // b + (a % b > 0)

while True:
    if ub == lb:
        print(ub)
        exit()
    target = (ub+lb) // 2
    tmp = 0
    for a in al:
        if a * a <= target:
            tmp -= 1
        if a == 0:
            if target >= 0:
                tmp += n
        elif a < 0:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += n - idx
        else:
            k = target // a
            idx = bisect.bisect_right(al, k)
            tmp += idx
    tmp = tmp // 2
    if tmp >= K:
        ub = target
    else:
        lb = target + 1