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:
N, K = input().split()
N = int(N)
K = int(K)
A_list = input().split()
A_array = np.array([int(Ai) for Ai in A_list])

A_minus_array = A_array[A_array < 0]
A_zero_array = A_array[A_array == 0]
A_plus_array = A_array[A_array > 0]

A_minus_num = len(A_minus_array)
A_zero_num = len(A_zero_array)
A_plus_num = len(A_plus_array)

count_multi1 = int(A_minus_num*A_plus_num)
count_multi2 = int(A_minus_num*A_plus_num + A_zero_num*(A_minus_num+A_plus_num) + A_zero_num*(A_zero_num-1)/2 if A_zero_num > 1\
                else A_minus_num*A_plus_num + A_zero_num*(A_minus_num+A_plus_num))

if count_multi1 > K:
    multi_A = []
    for A_minus in A_minus_array:
        for A_plus in A_plus_array:
            multi_A.append(A_minus*A_plus)
    print(sorted(multi_A)[K-1])
elif count_multi2 > K:
    print(0)
else:
    K_ = K - count_multi2
    A_minus_array_ = sorted(np.abs(A_minus_array))
    A_plus_array_ = sorted(np.abs(A_plus_array))
    multi_A1 = []
    multi_A2 = []
    if A_minus_num > 1:
        for i in range(A_minus_num):
            for j in range(i+1, A_minus_num):
                multi_A1.append(A_minus_array_[i]*A_minus_array_[j])
    if A_plus_num > 1:
        for i in range(A_plus_num):
            for j in range(i+1, A_plus_num):
                multi_A2.append(A_plus_array_[i]*A_plus_array_[j])
    multi_A = multi_A1 + multi_A2
    multi_A = sorted(multi_A)
    print(multi_A[K_-1])

Submission status: Runtime Error

Solution code:
def resu(li, r):
    a = li[0]
    del li[0]
    for i in li:
        r.append(a*i)
    if len(li)>1:
        return resu(li,r)
    else:
        return r

a, b= map(int, input().split(" "))
ls = list(map(int,input().split(" ")))
nm = []
print(sorted(resu(ls,nm))[b-1])

Submission status: Runtime Error

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

def mul_of_all_pairs(lst):
    def mul_of_car_and_rest(lst):
        return list(map(lambda x: lst[0]*x, lst[1:]))

    def iter(lst):
        if len(lst)>2:
            return mul_of_car_and_rest(lst) + iter(lst[1:])
        elif len(lst)==2:
            return [lst[0] * lst[1]]

    return iter(lst)

print (sorted(mul_of_all_pairs(A))[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = np.array(A)
b = np.array(A)
m = np.outer(a, b)

ans = []
ans_extend = ans.extend

for i in range(N-1):
    ans_extend(m[i,i+1:])

ans = sorted(ans)    

print(ans[K-1])

Submission status: Runtime Error

Solution code:
def main():
  N,K =map(int, input().split())
  A=list(map(int, input().split()))
  
  zero, ng, ps =[],[],[]
  for a in A:
    if a==0:
      zero.append(0)
    elif a<0:
      ng.append(a)
    else:
      ps.append(a)

  mins = len(ng)*len(ps)
  zeros = len(zero)*(len(ng)+len(ps) + (len(zero) -1)//2)
  
  
  B=[]
  if K<=mins:
    for v in ng:
      B.extend([v*j for j in ps])
    print(sorted(B)[K-1])
  elif K <=mins+zeros:
    print(0)
  else:
    for i,v in enumerate(ng):
      B.extend([v*j for j in ng[i+1:]])
    for i,v in enumerate(ps):
      B.extend([v*j for j in ps[i+1:]])
    print(sorted(B)[K-mins-zeros-1])
    

main()

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int, input().split(" "))
A = np.array(list(map(int, input().split(" "))))

t = np.array([
    A * A[i]
    for i in range(N)
])

t = np.tril(t, -1)
t = t.flatten()

print(int(np.sort(t)[K - 1]))

Submission status: Runtime Error

Solution code:
def main():
  import numpy as np
  N,K =map(int, input().split())
  A=list(map(int, input().split()))
  
  A=np.array(A)
  zero = A[A==0]
  ng = A[A<0]
  ps = A[A>0]
  mins = len(ng)*len(ps)
  zeros = len(zero)*(len(ng)+len(ps)) + (len(zero)**2 -len(zero))//2
  
  
  B=[]
  if K<mins:
    for v in ng:
      B.extend([v*j for j in ps])
    print(sorted(B)[K-1])
  elif K <mins+zeros:
    print(0)
  else:
    for i,v in enumerate(ng):
      B.extend([v*j for j in ng[i+1:]])
    for i,v in enumerate(ps):
      B.extend([v*j for j in ps[i+1:]])
    print(sorted(B)[K-mins-zeros-1])
    

main()

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
u = 2*10**9
d = -u
import bisect
for i in range(100):
    x = (u+d)//2
    k = 0
    for j in range(N):
        a = A[i]
        b = bisect.bisect_right(A,a)
        k += b
    if k >= K:
        u = x
    else:
        d = x
print(d+1)

Submission status: Runtime Error

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

# As を小さい順に並べて、プラスとマイナスに分ける
As.sort()
for i in range(N):
    if As[i] >= 0:
        bound = i
        break

As_plus = As[bound:]
As_minus = As[:bound]

# 正の世界で考える
if len(As_plus) * len(As_minus) < K:
    dict = {'value': 5, 'plus': True}



else:
    # 負の世界で考える
    # As_plus => [95, 43, 2, ,,,]
    # As_minus => [-95, -43, -2, ,,,]
    As_plus.sort(reverse=True)
    i_plus = 0
    i_minus = 0
    while (i_plus+1) * (i_minus+1) < K:
        if i_plus + 1 < len(As_plus):
            i_plus += 1
        if i_minus + 1 < len(As_minus):
            i_minus += 1

    kouho = []
    # i_minusを固定、As_plusを動かしていく
    for i in range(i_plus):
        kouho.append(As_plus[i] * As_minus[i_minus])
    # i_plusを固定、As_minusを動かしていく
    for i in range(i_minus):
        kouho.append(As_plus[i_plus] * As_minus[i])

    kouho.sort()  # => [-298, -123, -110,,,,]
    #print(kouho)
    print(kouho[(K-1) - i_plus * i_minus])

Submission status: Runtime Error

Solution code:
n,k=(int(x) for x in input().split())
list1 = list(map(int, input().split()))
list2=[]
for i in range(n-1):
	for j in range(i+1,n):
		list2.append(list1[i]*list1[j])
list2.sort()
print(list2[k])

Submission status: Runtime Error

Solution code:
def main():
    n,k=map(int,input().split())
    A=tuple(map(int,input().split()))
    P=[]
    N=[]
    c=n*(n-1)//2
    for a in A:
        if a>=0:
            P.append(a)
        else:
            N.append(a)
    s=len(P)*len(N)
    x=0
    if s>k:
        L=[0]*s
        for p in P:
            for num in N:
                L[x]=p*num
                x+=1
        print(sorted(L)[k-1])
    else:
        m=(len(N)*(len(N)-1)+len(P)*(len(P)-1))//2
        L=[0]*m
        for i in range(len(N)-1):
            for j in range(i+1,len(N)):
                L[x]=N[i]*N[j]
                x+=1
        for i in range(len(P)-1):
            for j in range(i+1,len(P)):
                L[x]=P[i]*P[j]
                x+=1
        print(sorted(L)[::-1][c-k])
main()

Submission status: Runtime Error

Solution code:
import math
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()

roop_range = int(math.sqrt(k)) + 10

a_list_ans = []
for i in range(roop_range):
    for l in range(1,(n-i)):
        a_list_ans.append(a_list[i]*a_list[i+l])

a_list_ans.sort()
print(a_list_ans[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np
N,K=map(int,input().split())
A = np.array(list(map(int,input().split())))
A = A.reshape(N,1)
A_ = A.reshape(1,N)
prd = A*A_
prd = np.tril(prd, k=-1)
ls = []
for i in range(N):
  for j in range(i):
    ls.append(prd[i,j])
print(sorted(ls)[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.ones((n+1, n+1), dtype=np.int)
a_array_t = np.zeros((n, n), dtype=np.int)
ans_array = np.zeros(int(n*(n-1)/2), dtype=np.int)

for i in range(n):
  a_array[i+1,0]=a[i]
  a_array[0,i+1]=a[i]

for i in range(n+1):
  a_array[i,1:] = a_array[0,1:]*a_array[i,0]

a_array_t[:,:] = a_array[1:, 1:]
# print(a_array_t)

if n > 2:
  j=0
  for i in range(1, n):
    ans_array[j:j+i] = a_array_t[-i-1, -i:]
    j += i
else:
  ans_array[0] = a_array[0,1]

ans_sort = np.sort(ans_array)

print(ans_sort[k])

Submission status: Runtime Error

Solution code:
    #include<iostream>
    #include<string>
    #include<iomanip>
    #include<cmath>
    #include<vector>
    #include<algorithm>
     
    using namespace std;
     
    #define int long long
    #define endl "\n"
     
    constexpr long long INF = (long long)1e18;
    constexpr long long MOD = 1'000'000'007; 
     
    string yn(bool f){return f?"Yes":"No";}
    string YN(bool f){return f?"YES":"NO";}
     
    #define f first
    #define s second
     
    int N, K;
    vector<pair<int,int>> A;
    int minimum = INF, maximum = -INF;
     
    int check(int num){
    	int con = 0;
    	
    	// if(num > maximum*maximum) return N*N;
    	
    	// cout<<"=++++++++++++++++++++++++++++++++++   "<<num<<endl;
    	for(int i = 0; i < N; i++){
    		// cout<<"<> "<<i<<" A "<<A[i].f<<" con "<<con<<endl;
    		// if(A[i].f == 0) {
    			// if(num >= 0) con += max(i-1,0ll);
    		// }else if(A[i].f >= 0 && num >= 0){
    			// pair<int,int> x = {num / A[i].f, INF};
    			// int temp, temp2;
    			
    			
    			// temp = upper_bound(A.begin(), A.end(), x) - A.begin();
    			
    			// cout<<temp<<" [+] "<<i<<" x "<<x.f<<endl;
    			// con += max(0ll,min(temp, i-1));
    		// } else if(A[i].f < 0 && num < 0){
    			// pair<int,int> x = {-((long long)abs(num) + abs(A[i].f) - 1)/ abs(A[i].f), INF};
    			// int temp, temp2;
    			
    			// temp = upper_bound(A.begin(), A.end(), x) - A.begin();
    			
    			// cout<<temp<<" (-) "<<i<<" x "<<x.f<<endl;
    			// con += max(0ll,min(temp, i-1));
    		// } 
    		if(A[i].f == 0) {
    			// cout<<"000 "<<endl;
    			if(num >= 0) { 
    				// con += max(0ll,min(temp, i));
    				con += max(i,0ll);
    				// cout<<max(i,0ll)<<endl;
    			} else {
    				// cout<<0<<endl;
    			}
    		}else if(A[i].f >= 0 && num >= 0){
    			pair<int,int> x = {num / A[i].f, INF};
    			int temp, temp2;
    			
    			
    			temp = upper_bound(A.begin(), A.end(), x) - A.begin();
    			
    			// cout<<temp<<" [+0] "<<i<<" x "<<x.f<<" "<<min(temp, i)<<endl;
    			
    			con += max(0ll,min(temp, i));
    			// con += min(temp, i);
    		} else if(A[i].f < 0 && num >= 0){
    			pair<int,int> x = {-((long long)abs(num) + abs(A[i].f-1)-1)/ abs(A[i].f), INF};
    			// pair<int,int> x = {-((long long)abs(num) + abs(A[i].f)-1)/ abs(A[i].f), -INF};
    			// pair<int,int> x = {(num)/ A[i].f, INF};
    			int temp, temp2;
    			
    			temp = i - (upper_bound(A.begin(), A.end(), x) - A.begin());
    			// temp = i - (lower_bound(A.begin(), A.end(), x) - A.begin());
    			
    			// cout<<temp<<" (-1) "<<i<<" x "<<x.f<<" "<<min(temp, i)<<endl;
    			con += max(0ll,min(temp, i));
    			// con += min(temp, i);
    		} else if(A[i].f > 0 && num < 0){
    			pair<int,int> x = {-((long long)abs(num) + abs(A[i].f) - 1)/ abs(A[i].f), INF};
    			int temp, temp2;
    			
    			temp = upper_bound(A.begin(), A.end(), x) - A.begin();
    			
    			// cout<<temp<<" (-2) "<<i<<" x "<<x.f<<" "<<min(temp, i)<<endl;
    			con += max(0ll,min(temp, i));
    			// con += min(temp, i);
    		}
    		
    		int zz = 0;
    		for(int j = 0; j < i ; j++){
    			if(num >= A[i].f * A[j].f) zz++;
    		}
    		
    		// cout<<"TTTTTT "<<zz<<endl;
    	}
    	
    	return con;
    }
     
    int check2(int num){
    	int con = 0;
    	
    	for(int i = 0; i < N; i++){
    		for(int j = 0; j < i ; j++){
    			if(num >= A[i].f * A[j].f) con++;
    		}
    	}
    	
    	return con;
    }
     
    signed main(){
    	// cin.tie(nullptr);
    	// ios::sync_with_stdio(false);
    	// cout<<fixed<<setprecision(10);
    	
    	
    	cin>>N>>K;
    	
    	A.resize(N);
    	
    	for(int i = 0; i < N; i++){
    		cin>>A[i].f;
    		minimum = min(A[i].f, minimum);
    		maximum = max(A[i].f, maximum);
    	}
    	
    	sort(A.begin(), A.end());
    	
    	for(int i = 1; i < N; i++){
    		if(A[i-1].f == A[i].f) A[i].s = A[i-1].s+1;
    	}
    	
    	// for(int i = -12; i <= 10; i++){
    		// cout<<"i = "<<i<<" "<<check(i)<<" "<<check2(i)<<endl;
    	// }
    	
    	// int l = (long long)-abs(minimum) *  (long long)abs(minimum), h = (long long)abs(maximum)*(long long)abs(maximum)+10, m;
    	// int l = (long long)-abs(minimum) *  (long long)abs(minimum), h = (long long)abs(maximum)*(long long)abs(maximum)+10, m;
    	int l = -INF, h = INF, m;
    	while(l+1<h){
    		m = (l+h)/2;
    		int temp = check(m);
    		// cout<<"l = "<<l<<" h = "<<h<<endl;
    		
    		// cout<<"m "<<m<<" "<<temp<<endl;
    		// string hogehoge;
    		// cin>>hogehoge;
     
    		if (temp < K) {
    			l = m;
    		} else {
    			h = m;
    		}
    	}
    	
    	
    	// cout<<l<<" "<<h<<endl;
    	cout<<h<<endl;
    	
    	return 0;
    }

Submission status: Runtime Error

Solution code:
n=int(input())
k=int(input())

list1=[]
list2=[]
for i in range(n):
    a=int(input())
    list1.append(a)
for i in range(0,n):
    for j in range(i+1,n):
        list2.append(list1[i]*list1[j])

list2.sort()
print(list2[k-1])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
po = []
ng = []
zr = 0
for i in range(n):
  if a[i]>0:
    po.append(a[i])
  elif a[i]<0:
    ng.append(a[i])
  elif a[i]==0:
    zr += 1
lp=len(po)
ln=len(ng)
negn=lp*ln
zern=zr*(n-zr)+zr*(zr-1)//2

if k <= negn:
  p=[0]*negn
  c=0
  for i in range(lp):
    for j in range(ln):
      p[c]=po[i]*ng[j]
      c+=1
  p.sort()
  print(p[k-1])
elif negn < k <= negn+zern:
  print(0)
else:
  p=[0]*(n*(n-1)//2-negn-zern)
  c=0
  for i in range(lp-1):
    for j in range(i+1, lp):
      p[c]=po[i]*po[j]
      c+=1
  for i in range(ln-1):
    for j in range(i+1, ln):
      p[c]=ng[i]*ng[j]
      c+=1
  p.sort()
  print(p[k-1-negn-zern])

Submission status: Runtime Error

Solution code:
import math
n,k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()

roop_range = int(math.sqrt(k) + 10)

a_list_ans = []
for i in range(roop_range):
    for l in range(1,(roop_range-i)):
        a_list_ans.append(a_list[i]*a_list[i+l])

a_list_ans.sort()
print(a_list_ans[k-1])

Submission status: Runtime Error

Solution code:
    #include<iostream>
    #include<iomanip>
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<vector>
    #include<algorithm>
    #include<cmath>
    #include<string>
    #include<queue>
    #include<stack>
     
    using namespace std;
     
    typedef long long ll;
    typedef pair<ll, ll> pii;
    typedef pair<ll, bool> pib;
     
    typedef vector<bool> vb;
     
    typedef vector<ll> vi;
    typedef vector<vi> vvi;
    typedef vector<vvi> vvvi;
     
    typedef vector<pii> vpii;
    typedef vector<vpii> vvpii;
     
    typedef vector<double> vf;
     
    typedef queue<ll> qi;
     
    typedef long double ld;
     
    #define mp make_pair
    #define pb push_back
     
    #define rep(i, N) for(ll i = 0; i < N; i++)
    #define repa(i, a, N) for(ll i = a; i < N; i++)
    #define repr(i, N) for(ll i = N-1; i >= 0; i--)
     
    #define drep(i, N, j, M) rep(i, N) rep(j, M)
    #define trep(i, N, j, M, k, L) rep(i, N) rep(j, M) rep(k, L)
     
    #define all(A) A.begin(), A.end()
    template<class t, class u>
    ostream& operator<<(ostream& os, const pair<t, u>& p) {
    	return os << "{" << p.first << "," << p.second << "}";
    }
     
    template<class t>
    ostream& operator<<(ostream& os, const vector<t>& v) {
    	os << "{";
    	for (auto e : v)os << e << ",";
    	return os << "}";
    }
     
    template<class t, class u>
    ostream& operator<<(ostream& os, const unordered_map<t, u>& m) {
    	os << "{";
    	for (auto itr = m.begin(); itr != m.end(); ++itr) {
    		os << "(" << itr->first << ", " << itr->second << "), ";
    	}
    	return os << "}";
    }
     
    template<class t>
    ostream& operator<<(ostream& os, const set<t>& m) {
    	os << "{";
    	for (auto itr = m.begin(); itr != m.end(); ++itr) {
    		os << *itr << ", ";
    	}
    	return os << "}";
    }
     
    template<class t>
    ostream& operator<<(ostream& os, const multiset<t>& m) {
    	os << "{";
    	for (auto itr = m.begin(); itr != m.end(); ++itr) {
    		os << *itr << ", ";
    	}
    	return os << "}";
    }
     
     
    const ll LLMAX = numeric_limits<long long>::max() / 3;
    const double DMAX = numeric_limits<double>::max() / 3;
     
    const double PI = 3.141592653589793;
    const ll MOD = 1e9 + 7;
    // const ll MOD = 998244353;
     
    template <std::int_fast64_t Modulus> class modint {
    	using i64 = std::int_fast64_t;
     
    public:
    	i64 a;
     
    	constexpr modint(const i64 x = 0) noexcept : a(x % Modulus) {}
    	constexpr i64 &value() noexcept { return a; }
    	constexpr const i64 &value() const noexcept { return a; }
    	constexpr modint operator+(const modint rhs) const noexcept {
    		return modint(*this) += rhs;
    	}
    	constexpr modint operator-(const modint rhs) const noexcept {
    		return modint(*this) -= rhs;
    	}
    	constexpr modint operator*(const modint rhs) const noexcept {
    		return modint(*this) *= rhs;
    	}
    	constexpr modint operator/(const modint rhs) const noexcept {
    		return modint(*this) /= rhs;
    	}
    	constexpr modint &operator+=(const modint rhs) noexcept {
    		a += rhs.a;
    		if (a >= Modulus) {
    			a -= Modulus;
    		}
    		return *this;
    	}
    	constexpr modint &operator-=(const modint rhs) noexcept {
    		if (a < rhs.a) {
    			a += Modulus;
    		}
    		a -= rhs.a;
    		return *this;
    	}
    	constexpr modint &operator*=(const modint rhs) noexcept {
    		a = a * rhs.a % Modulus;
    		return *this;
    	}
    	constexpr modint &operator/=(modint rhs) noexcept {
    		i64 exp = Modulus - 2;
    		while (exp) {
    			if (exp % 2) {
    				*this *= rhs;
    			}
    			rhs *= rhs;
    			exp /= 2;
    		}
    		return *this;
    	}
    };
     
    template<std::int_fast64_t Modulus>
    ostream& operator<<(ostream& os, const modint<Modulus>& m) {
    	return os << (m.a + Modulus) % Modulus;
    }
     
    typedef modint<MOD> mod;
     
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
     
    ll PowInt(ll a, ll n) {
    	ll t = 1;
    	rep(i, n) {
    		t *= a;
    	}
    	return t;
    }
     
    ll x;
     
    ll N, M, K;
     
    vi A(0);
    vi Nega(0);
    vi Posi(0);
     
    bool isOK(ll a, ll k, ll mid) {
    	ll low = 0;
    	ll same = 0;
    	for (auto p : Posi) {
    		ll m;
    		if (mid % p == 0) {
    			m = mid / p;
    			auto litr = lower_bound(all(Nega), m);
    			low += litr - Nega.begin();
    		}
    		else {
    			m = mid / p;
    			auto litr = lower_bound(all(Nega), m + 1);
    			low += litr - Nega.begin();
    		}
     
    		if (low >= k) {
    			return true;
    		}
    	}
     
    	return false;
    }
     
    bool isOK2(ll xx, ll k, ll mid) {
    	ll low = 0;
    	ll same = 0;
    	ll i = 0;
    	for (auto p : Posi) {
    		ll m;
    		auto start = Posi.begin() + i + 1;
    		i++;
    		if (mid % p == 0) {
    			m = mid / p;
    			auto litr = lower_bound(start, Posi.end(), m);
    			low += litr - start;
    		}
    		else {
    			m = mid / p;
    			auto litr = lower_bound(start, Posi.end(), m + 1);
    			low += litr - start;
    		}
     
    		if (low >= k) {
    			return true;
    		}
    	}
     
    	i = 0;
    	for (auto p : Nega) {
    		ll m;
    		auto start = Nega.begin() + i + 1;
    		i++;
    		if (mid % p == 0) {
    			m = mid / p;
    			auto litr = lower_bound(start, Nega.end(), m);
    			low += litr - start;
    		}
    		else {
    			m = mid / p;
    			auto litr = lower_bound(start, Nega.end(), m + 1);
    			low += litr - start;
    		}
     
    		if (low >= k) {
    			return true;
    		}
    	}
     
    	return false;
    }
     
    ll binary_search(ll a, ll k) {
    	ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    	ll right = a; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
     
    	/* どんな二分探索でもここの書き方を変えずにできる！ */
    	while (right - left > 1) {
    		ll mid = left + (right - left) / 2;
     
    		if (isOK(a, k, mid))
    			right = mid;
    		else left = mid;
    	}
     
    	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    	return left;
    }
     
    ll binary_search2(ll a, ll k) {
    	ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    	ll right = a; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
     
    	/* どんな二分探索でもここの書き方を変えずにできる！ */
    	while (right - left > 1) {
    		ll mid = left + (right - left) / 2;
     
    		if (isOK2(a, k, mid))
    			right = mid;
    		else left = mid;
    	}
     
    	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    	return left;
    }
     
    void No() { cout << "No" << endl; }
    void Yes() { cout << "Yes" << endl; }
    void NO() { cout << "NO" << endl; }
    void YES() { cout << "YES" << endl; }
     
    int main() {
    	cin >> N >> K;
    	ll n = 0;
    	ll p = 0;
    	ll z = 0;
    	rep(i, N) {
    		ll a;
    		cin >> a;
    		A.pb(a);
    		if (A[i] > 0) {
    			p++;
    			Posi.pb(A[i]);
    		}
    		if (A[i] < 0) {
    			n++;
    			A[i] = -A[i];
    			Nega.pb(A[i]);
    		}
    	}
    	z = N - p - n;
    	sort(all(A));
    	sort(all(Nega));
    	sort(all(Posi));
     
     
    	ll ans;
    	if (p * n >= K) {
    		// 負
    		K = p * n - K + 1;
     
    		x = 1e18+1;
    		ans = -binary_search(x, K);
    	}
    	else if (p * n + z * (N - z) + z * (z - 1) / 2 >= K) {
    		ans = 0;
    	}
    	else {
    		// 正
    		x = 1e18+1;
    		K = K - p * n -z * (N - z) - z * (z - 1) / 2;
    		ans = binary_search2(x, K);
    	}
     
    	cout << ans << endl;
     
    	return 0;
    }

Submission status: Runtime Error

Solution code:
def solve():
    N, K = [int(x) for x in input().split()]
    a_lst = [int(x) for x in input().split()]
    ans = []
    a_lst.sort()
    n_m = n_z = n_p = 0
    a_m = a_z = a_p = 0
    for a in a_lst:
        if a < 0: n_m += 1
        if a == 0: n_z += 1
        if a > 0: n_p += 1
    a_m = n_m * n_p
    a_z = n_z * (n_m + n_p) + n_z * (n_z - 1)//2
    a_p = N*(N-1)//2 - a_m - a_z
    if K <= a_m:
        ans = [0]*a_m
        k = 0
        for i in range(n_m):
            for j in range(n_m + n_z, N):
                ans[k] = a_lst[i] * a_lst[j]
                k += 1
        ans.sort()
        return ans[K - 1]
    elif a_m < K <= a_m + a_z:
        return 0
    else:
        ans = [0]*a_p
        k = 0
        if n_m > 0:
            for i in range(n_m - 1):
                for j in range(i + 1, n_m):
                    ans[k] = a_lst[i] * a_lst[j]
                    k += 1
        for i in range(n_m + n_z, N - 1):
            for j in range(i + 1, N):
                ans[k] = a_lst[i] * a_lst[j]
                k += 1
        ans.sort()
        return ans[K - a_m - a_z - 1]

if __name__ == '__main__':
    print(solve())

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
# process
B = []
for x, y in itertools.combinations(A, 2):
    B.append(x*y)
 
B.sort()
 
# output
print(B[K-1])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, A):
    ans = 0
    A.sort()
    pi = bisect.bisect_right(A, 0)
    N = A[:pi]
    P = A[pi:]

    ans = None
    if M <=  len(N) * len(P):
        L = [(abs(v), -1) for v in N] + [(v, 1) for v in P]
        L.sort(reverse=True)
        n = 0
        p = 0
        c = 0
        nl = []
        pl =[]
        for v, s in L:
            a = 0
            if s == -1:
                n += 1
                a = p
                b = -v
                nl.append(-v)
            else:
                p += 1
                a = p
                b = v
                pl.append(v)
            if c + a >= M:
                cand = []
                for d in nl if s == 1 else pl:
                    cand.append(d*b)
                cand.sort()
                return cand[M - a - 1]
            else:
                c += a
    else:
        M -= len(N) * len(P)
        L = [(abs(v), -1) for v in N] + [(v, 1) for v in P]
        L.sort(reverse=True)
        n = 0
        p = 0
        c = 0
        nl = []
        pl = []
        for v, s in L:
            a = 0
            if s == -1:
                n += 1
                a = p
                b = -v
                nl.append(-v)
            else:
                p += 1
                a = p
                b = v
                pl.append(v)
            if c + a >= M:
                cand = []
                for d in nl if s == -1 else pl:
                    cand.append(d*b)
                cand.sort()
                return cand[M - a - 1]
            else:
                c += a
    return ans


def f(N, M, A):
    ans = []
    A.sort()
    for i in range(N):
        for j in range(i+1, N):
            print(A[i], A[j], A[i] * A[j])
            ans.append(A[i]*A[j])
    ans.sort()
    return ans[M-1]

def main():
    N, M = read_int_n()
    A = read_int_n()

    print(slv(N, M, A))
    print(f(N, M, A))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#未完成
n,k,*a,=map(int,open(0).read().split())
a.sort()
zero=0
for i in range(n):
    if a[i]>0:
        negative=a[:i-zero]
        break
    if a[i]==0:
        zero+=1
positive=a[i:]
# print(positive)
# print(zero)
# print(negative)
nega,posi=len(negative),len(positive)
if k<=nega*posi:
    # print(negative[k//posi]*positive[k%posi])
elif k<=n*(n-1)//2-posi*(posi-1)//2:
    # print(k,nega*posi+zero*(n-zero))
    print(0)
else:
    
    k-=n*(n-1)//2-posi*(posi-1)//2
    p=posi
    print("k=",k,p)
    # for i in range(posi):
    #     if k<=p:
    #         print(positive[i]*positive[i+k])
    #         break
    #     k-=p
    #     p-=1
    # print("mada")

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.ones((n+1, n+1), dtype=np.int)
a_array_t = np.zeros((n, n), dtype=np.int)
ans_array = np.zeros(int(n*(n-1)/2), dtype=np.int)

for i in range(n):
  a_array[i+1,0]=a[i]
  a_array[0,i+1]=a[i]

for i in range(n+1):
  a_array[i,1:] = a_array[0,1:]*a_array[i,0]

a_array_t[:,:] = a_array[1:, 1:]
# print(a_array_t)

j=0
for i in range(1, n):
  ans_array[j:j+i] = a_array_t[-i-1, -i:]
  j += i

ans_sort = np.sort(ans_array)

print(ans_sort[k-1])

Submission status: Runtime Error

Solution code:
n,k=(int(x) for x in input().split())
list1 = list(map(int, input().split()))
list1.sort()
list2 = [n-1]*n
list3=[]
for j in range(n):
	list3.append(list1[j]*list1[list2[j]])
for j in range(k):
	max1=list3.index(min(list3))
	list2[max1]-=1
	list3[max1]=list1[max1]*list1[list2[max1]]
print(list3[max1])

Submission status: Runtime Error

Solution code:
import numpy as np

N, K = map(int,input().split())

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

a = np.array(A)
b = np.array(A)

m = np.outer(a, b)

ans = []
n = 1

for i in m:
    ans.extend(i[n:])
    n += 1

ans = sorted(ans)    

print(ans[K-1])

Submission status: Runtime Error

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

neg = []
pos = []
for a in A:
    if a < 0:
        neg.append(a)
    else:
        pos.append(a)
num_neg = len(neg) * len(pos)
num_pos = len(neg) * (len(neg) - 1) / 2 + len(pos) * (len(pos) - 1) / 2

if k < num_neg:
    neg.sort()
    pos.sort(reverse=True)
    d = k // len(neg)
    s = k % len(pos)
    ans = neg[d] * pos[s]
else:
    k -= num_neg
    neg = sorted([abs(i) for i in neg])
    pos.sort()
    neg.append(float('infinity'))
    pos.append(float('infinity'))
    while True:
        if neg[0] < pos[0]:
            if k > len(neg) - 2:
                k = k - len(neg) + 2
                neg = neg[1:]
            else:
                ans = neg[0] * neg[k]
                break
        else:
            if k > len(pos) - 2:
                k = k - len(pos) + 2
                pos = pos[1:]
            else:
                ans = ans = pos[0] * pos[k]
                break
print(ans)

Submission status: Runtime Error

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

p = []
m = []

for i in range(N):
    if A[i] >= 0:
        p.append(A[i])
    else:
        m.append(A[i])
        
number = []

from math import factorial
a = factorial(N) / factorial(2) / factorial(N - 2)


if len(p)*len(m) >= K:
    for i in range(len(p)):
        for j in range(len(m)):
            number.append(p[i]*m[i])
            
    number.sort()
    print(number[K-1])
    
else:
    for i in range(0,len(p)-1):
        for j in range(i+1,len(p)):
            number.append(p[i]*p[j])
            
    for i in range(0,len(m)-1):
        for j in range(i+1,len(m)):
            number.append(m[i]*m[j])
            
    number.sort()
    print(number[K-len(p)*len(m)-1])

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

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

info.sort()
another_info = info.copy()

info = np.array(info)
another_info = np.array(another_info)

info = info.reshape(n,1)
another_info = another_info.reshape(1, n)

ans_arr = info * another_info

print(ans_arr)
ans_arr = ans_arr.tolist()

for i in range(n):
    ans_arr[i] = ans_arr[i][i:]
ans_arr = list(itertools.chain.from_iterable(ans_arr))
ans_arr.sort()
print(ans_arr[k-1])