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:
import sys

N, K = map(int, sys.stdin.readline().split())
A = tuple(map(int, sys.stdin.readline().split()))

UnderZeroA = tuple([a for a in A if a < 0])
ZeroA = tuple([a for a in A if a == 0])
OverZeroA = tuple([a for a in A if a > 0])

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_Zero

if K <= L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i, u in enumerate(UnderZeroA):
        for j, o in enumerate(OverZeroA):
            arr[i*L_OverZeroA+j] = u*o
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    if L_UnderZeroA > 0:
        count=0
        for i in range(L_UnderZeroA - 1):
            for j in range(i+1, L_UnderZeroA):
                #arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
                arr1[count] = UnderZeroA[i]*UnderZeroA[j]
                count += 1
    if L_OverZeroA > 0:
        count=0
        for i in range(L_OverZeroA - 1):
            for j in range(i+1, L_OverZeroA):
                #arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
                arr2[count] = OverZeroA[i]*OverZeroA[j]
                count += 1
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero - L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
A = tuple(map(int, sys.stdin.readline().split()))

UnderZeroA = tuple([a for a in A if a < 0])
ZeroA = tuple([a for a in A if a == 0])
OverZeroA = tuple([a for a in A if a > 0])

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_Zero

if K <= L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i, u in enumerate(UnderZeroA):
        for j, o in enumerate(OverZeroA):
            arr[i*L_OverZeroA+j] = u*o
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    if L_UnderZeroA > 0:
        for i in range(L_UnderZeroA - 1):
            for j in range(i+1, L_UnderZeroA):
                arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    if L_OverZeroA > 0:
        for i in range(L_OverZeroA - 1):
            for j in range(i+1, L_OverZeroA):
                arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero - L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
A = tuple(map(int, sys.stdin.readline().split()))

UnderZeroA = tuple([a for a in A if a < 0])
ZeroA = tuple([a for a in A if a == 0])
OverZeroA = tuple([a for a in A if a > 0])

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_Zero

if K < L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i, u in enumerate(UnderZeroA):
        for j, o in enumerate(OverZeroA):
            arr[i*L_OverZeroA+j] = u*o
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    if L_UnderZeroA > 0:
        for i in range(L_UnderZeroA - 1):
            for j in range(i+1, L_UnderZeroA):
                arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    if L_OverZeroA > 0:
        for i in range(L_OverZeroA - 1):
            for j in range(i+1, L_OverZeroA):
                arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero - L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

UnderZeroA = [a for a in A if a < 0]
ZeroA = [a for a in A if a == 0]
OverZeroA = [a for a in A if a > 0]

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_UnderZero

if K < L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i in range(L_UnderZeroA):
        for j in range(L_OverZeroA):
            arr[i*L_OverZeroA+j] = UnderZeroA[i]*OverZeroA[j]
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    if L_UnderZeroA > 0:
        for i in range(L_UnderZeroA - 1):
            for j in range(i+1, L_UnderZeroA):
                arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    if L_OverZeroA > 0:
        for i in range(L_OverZeroA - 1):
            for j in range(i+1, L_OverZeroA):
                arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero -L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

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

UnderZeroA = [a for a in A if a < 0]
ZeroA = [a for a in A if a == 0]
OverZeroA = [a for a in A if a > 0]

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_UnderZero

if K < L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i in range(L_UnderZeroA):
        for j in range(L_OverZeroA):
            arr[i*L_OverZeroA+j] = UnderZeroA[i]*OverZeroA[j]
    arr.sort()
    print(arr[K-1])
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    for i in range(L_UnderZeroA - 1):
        for j in range(i+1, L_UnderZeroA):
            arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    for i in range(L_OverZeroA - 1):
        for j in range(i+1, L_OverZeroA):
            arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero -L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

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

UnderZeroA = [a for a in A if a < 0]
ZeroA = [a for a in A if a == 0]
OverZeroA = [a for a in A if a > 0]

L_UnderZeroA = len(UnderZeroA)
L_ZeroA = len(ZeroA)
L_OverZeroA = len(OverZeroA)

L_UnderZero = L_UnderZeroA*L_OverZeroA
L_Zero = L_ZeroA*(L_UnderZeroA + L_OverZeroA) + L_ZeroA*(L_ZeroA-1)//2
L_OverZero = N*(N-1)//2 - L_UnderZero - L_UnderZero

if K < L_UnderZero:
    arr = [None]*(L_UnderZeroA*L_OverZeroA)
    for i in range(L_UnderZeroA):
        for j in range(L_OverZeroA):
            arr[i*L_OverZeroA+j] = UnderZeroA[i]*OverZeroA[j]
    arr.sort()
elif K > L_UnderZero + L_Zero:
    arr1 = [None]*(L_UnderZeroA*(L_UnderZeroA - 1)//2)
    arr2 = [None]*(L_OverZeroA*(L_OverZeroA - 1)//2)
    for i in range(L_UnderZeroA - 1):
        for j in range(i+1, L_UnderZeroA):
            arr1[i*(L_UnderZeroA-1) + (j-i-1) - (i-1)*i//2] = UnderZeroA[i]*UnderZeroA[j]
    for i in range(L_OverZeroA - 1):
        for j in range(i+1, L_OverZeroA):
            arr2[i*(L_OverZeroA-1) + (j-i-1) - (i-1)*i//2] = OverZeroA[i]*OverZeroA[j]
    arr = arr1 + arr2
    arr.sort()
    index = K - L_UnderZero -L_Zero
    print(arr[index-1])
else:
    print(0)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

MAX = 10**18
MIN = -MAX

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()

  Ans, Aps, Azs = [], [], []
  for A in As:
    if A > 0:
      Aps.append(A)
    elif A == 0:
      Azs.append(A)
    else:
      Ans.append(A)

  def count(xs, ys, ub):
    c = 0
    r = len(ys) - 1
    for l in range(len(xs)):
      while xs[l] * ys[r] > ub and r >= 0:
        r -= 1
      c += r+1
    return c 

  def bs(l, r):
    while True:
      mid = (l+r) // 2
      if r - l <= 1:
        return r
      tot = 0
      
      tot += count(Aps, Aps, mid) - sum([1 for A in Aps if A**2 <= mid])
      tot += count(Ans[::-1], Ans[::-1], mid) - sum([1 for A in Ans if A**2 <= mid])
      tot //= 2

      if mid >=0:
        tot += (len(Aps) + len(Ans)) * len(Azs) + (len(Azs) * (len(Azs) - 1)) // 2
      tot += count(Aps[::-1], Ans, mid)
      
      if tot < k:
        l = mid
      else:
        r = mid
  
  print(bs(MIN-1, MAX+1))
    
    
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:

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

from bisect import bisect_right as bisect_left
#%%
A.sort()
m,z = 0,0,
for i in range(1,N):
    if A[i-1]<0 and A[i]>=0:
        m = i
        z = i
    elif A[i-1]==0 and A[i]>0:
        z = i

Am = A[:m]
Az = A[m:z]
Ap = A[z:]

# 負のリストを正に変換
revAm = [-a for a in reversed(Am)]

Lm = len(Am)
Lz = len(Az)
Lp = len(Ap)
bias = Lm*Lp + Lz*(Lm+Lp) + Lz*(Lz-1)//2

MAX = 10**18 + 1

def judge(x,key):
    # Ai*Aj <= xとなる組み合わせの個数を数える -> K個以上か？
    num = 0
    
    if x<0:
        #0との組は考えなくてよい
        #プラスとマイナスの組だけ考える
        
        nx = -x
        # revAm[i]*Ap[j] >= xとなる個数を数える
        
        for mm in revAm:
            eidx = bisect_left(Ap,nx/mm)-1
            num += Lp - eidx
        
    elif x>=0:
        #0以下となる個数は先に足す
        num += bias 
        if num>=key:
            return True  
        # 同符号の中でx以下の個数を数える
        for i,pp in enumerate(Ap):
            eidx = max(0,bisect_left(Ap, x/pp)-1)
            num += max(0,eidx-i)
        for i,mm in enumerate(revAm):
            eidx = max(0,bisect_left(revAm, x/mm)-1)
            num += max(0,eidx-i)
    if num>=key:
        return True
    else: 
        return False
            

def meguru(key):
    ok = MAX
    ng = -MAX
    
    while (abs(ok-ng)>1):
        mid = (ok+ng)//2
        if judge(mid,key):
            ok = mid
        else:
            ng = mid
    return ok
    

ans = meguru(K)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF = 1e18+18;
const ll MAX = 100005;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;


int main(){
    ll N, K;
    cin>>N>>K;
    vector<ll> A(N);

    for(int i=0; i<N; i++){
        cin>>A[i];
    }
    sort(A.begin(), A.end());

    ll Min=-1*1000000000000000000-1;
    ll Max=1*1000000000000000000+1;

    while(Max-Min>1){
      	ll Mid=Max+Min;
        Mid/=2;
        ll Sum=0;
        for(int i=0; i<N; i++){
            if(A[i]>0){
                ll X=((Mid>=0)?Mid/A[i]:((Mid+1)/A[i]-1));
                auto itr=upper_bound(A.begin(), A.end(), X);
                Sum+=distance(A.begin(), itr);
                if(X>=A[i])Sum--;
            }
            else if(A[i]<0){
                ll X=((Mid>=0)?Mid/A[i]:(Mid+1)/A[i]+1);
                auto itr=lower_bound(A.begin(), A.end(), X);
                Sum+=distance(itr, A.end());
                if(X<=A[i])Sum--;
            }
            else if(Mid>=0){
                Sum+=N-1;
            }

        }
        Sum/=2;
        if(Sum<K){
            Min=Mid;
        }
        else{
            Max=Mid;
        }
    }
    cout<<Max<<endl;
}
/*
    from collections import Counter
    n=int(input())
    s=[input() for _ in range(n)]
    d=Counter(s)
    m=max(d.values())
    keys = [k for k,v in d.items() if v==m]
    print("\n".join(sorted(keys)))
*/

Submission status: Runtime Error

Solution code:
  /*  n = list(map(int,input()))[::-1]
    n.append(0)

    for i in range(len(n)):
        if n[i] >= 6 or (n[i] == 5 and n[i+1] >= 5):
            n[i] = 10 - n[i]
            n[i+1] += 1

    print(sum(n)) */

    #include <bits/stdc++.h>
    using namespace std;

    struct Unionfind {
      // tree number
      vector<int> par;
      // tree rank
      vector<int> treerank;
      // constructor
      Unionfind(int n = 1) { stree(n + 1); }
      // make and initialization
      void stree(int n = 1) {
        par.assign(n, -1);
        treerank.assign(n, 0);
      }
      // search root
      int root(int x) {
        if(par[x] < 0) return x;
        return par[x] = root(par[x]);
      }
      // is same?
      bool issame(int x, int y) { return root(x) == root(y); }

      // add
      // already added, return 0
      bool uni(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y) return 0;
        if(treerank[x] > treerank[y]) swap(x, y);
        if(treerank[x] == treerank[y]) ++treerank[y];
        par[y] -= size(x);
        par[x] = y;
        return 1;
      }
      int size(int x) { return -par[root(x)]; }
    };

    struct bomb {
      int a;
      bool b;
      bomb(int _a = 0, bool _b = 0) : a(_a), b(_b) {}
      bool operator<(const bomb& r) const { return a < r.a; }
    };

    struct cod {
      int l, r;
    };

    int n, m;
    vector<bomb> bombs;
    vector<cod> v;
    vector<bool> dif, used;
    vector<int> res;
    vector<vector<int>> edges;
    Unionfind uf;

    bool solve();
    bool dfs(int now);

    int main() {
      cin >> n >> m;
      bombs.resize(n);
      for(int i = 0; i < n; ++i)
        cin >> bombs[i].a >> bombs[i].b;
      bombs.push_back({-1, 0});
      sort(bombs.begin(), bombs.end());
      bombs.push_back({(int)1e9 + 1, 0});
      v.resize(m);
      for(int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        l = lower_bound(bombs.begin(), bombs.end(),
                        bomb(l, 0)) -
            bombs.begin();
        r = upper_bound(bombs.begin(), bombs.end(),
                        bomb(r, 1)) -
            bombs.begin();
        v[i] = {l - 1, r - 1};
      }
      for(int i = 0; i < bombs.size() - 1; ++i)
        dif.push_back(bombs[i].b ^ bombs[i + 1].b);
      if(solve()) {
        cout << res.size() << endl;
        for(int i = 0; i < res.size(); ++i) {
          if(i != 0) cout << " ";
          cout << res[i] + 1;
        }
        cout << endl;
      }
      else
        cout << -1 << endl;
      return 0;
    }

    bool solve() {
      n = dif.size();
      uf = Unionfind(n);
      edges.resize(n);
      for(int i = 0; i < m; ++i)
        if(!uf.issame(v[i].l, v[i].r)) {
          uf.uni(v[i].l, v[i].r);
          edges[v[i].l].push_back(i);
          edges[v[i].r].push_back(i);
        }
      used.assign(n, 0);
      for(int i = 0; i < n; ++i)
        used[uf.root(i)] = used[uf.root(i)] ^ dif[i];
      for(int i = 0; i < n; ++i)
        if(used[i]) return 0;
      for(int i = 0; i < n; ++i)
        if(!used[i]) {
          used[i] = 1;
          dfs(i);
        }
      sort(res.begin(), res.end());
      return 1;
    }

    bool dfs(int now) {
      for(auto e : edges[now]) {
        int nextp;
        if(v[e].l == now)
          nextp = v[e].r;
        else
          nextp = v[e].l;
        if(used[nextp]) continue;
        used[nextp] = 1;
        if(dfs(nextp)) {
          res.push_back(e);
          dif[now] = dif[now] ^ 1;
        }
      }
      return dif[now];
    }

Submission status: Runtime Error

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

results = []
for i in range(N):
  for j in range(i+1, N):
    results.append(i,j)
    
print(results[K-1])

Submission status: Runtime Error

Solution code:
NandK = input()
NandK = NandK.split(' ')
N = int(NandK[0]) ; K = int(NandK[1])
anslist = []
A = input()
A = A.split(' ')
for k in range(len(A)):
    for j in range(k+1, len(A)):
        anslist.append(int(A[k]) * int(A[j]))
anslist.sort()
print(anslist[K])

Submission status: Runtime Error

Solution code:
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Runtime Error

Solution code:
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

#cn = len(mn)
#cp = len(mp)
#cz = len(mz)
#tcn = cn*cp

#if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
#    print(0)
#    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)

Submission status: Runtime Error

Solution code:
#標準入力からの値取得(N)
N, K = (int(x) for x in input().split())
TMP = [int(x) for x in input().split()]
#List:TMPから、値が0の要素を取り出して別Listに格納する
A = []
Z = 0
for row in TMP:
  if row == 0:
    Z += 1
  else:
    A.append(row)
#計算本体処理
ans = []
for i in range(0,len(A)-1):
  for j in range(i+1,len(A)):
    ans.append( A[i] * A[j] )
#0を突っ込む処理
ZC = []
ZC.append(0)
ZC *= int(((N*(N-1))/2) - ((len(A)*(len(A)-1)/2)))
ans.extend(ZC)
ans.sort()
print(ans[K-1])

Submission status: Runtime Error

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

import bisect 

a.sort()
zero_l = bisect.bisect_left(a, 0)
zero_r = bisect.bisect_right(a, 0)
nega = a[:zero_l]
posi = a[zero_r:]
zero = a[zero_l:zero_r]

def get_under(num):
  cnt = 0
  if num<0:
    for n_i in nega:
      cnt += len(posi) - bisect.bisect_left(posi, num/n_i) 
  elif num==0:
    cnt += len(posi) * len(nega)
    cnt += len(zero) * (n - len(zero)) + (len(zero)*len(zero)-len(zero))/2
  elif num>0:
    cnt += len(posi) * len(nega)
    cnt += len(zero) * (n - len(zero)) + (len(zero)*len(zero)-len(zero))/2
    cnt2 = 0
    for p_i in posi:
      cnt2 += bisect.bisect_right(posi, num/p_i)
      if p_i**2<=num:
        cnt2 -= 1
    for n_i in nega:
      cnt2 += len(nega) - bisect.bisect_left(nega, num/n_i) 
      if n_i**2<=num:
        cnt2 -= 1
    cnt2 = cnt2/2
    cnt += cnt2
  return cnt

def b_search(k, l, r):
  if not r>l:
    return r
  
  mid = (l+r)//2
  num_under = get_under(mid)
  #print(l,mid,r, num_under)
  if num_under<k:
    return b_search(k, mid+1, r)
  else:
    return b_search(k, l, mid)
    

max_v = max(min(nega)*min(nega), max(posi)*max(posi))
print(int(b_search(k, min(nega)*max(posi), max_v)))

Submission status: Runtime Error

Solution code:
NK=list(map(int, input().split()))
A=list(map(int, input().split()))
N=NK[0]
List=[]
i=0
Len=len(A)
while i<Len:
    j=i+1
    while j < Len:
      List.append(A[i]*A[j])
      j=j+1
    i=i+1
List.sort()
print(List[NK[1]])

Submission status: Runtime Error

Solution code:
NK=list(map(int, input().split()))
A=list(map(int, input().split()))
N=NK[0]
List=[]
i=0
Len=len(A)
while i<Len:
    j=i+1
    while j < Len:
      List.append(A[i]*A[j])
      j=j+1
    i=i+1
List.sort()
print(List)
print(List[NK[1]])

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int64_t N, K;
    cin >> N >> K;
    // printf("%lld, %lld\n", N, K);
    auto A = vector<int64_t>();
    A.reserve(N);
    for (int64_t i = 0 ; i < N; ++i) {
        cin >> A[i];
    }
    auto hq = priority_queue<int64_t, std::vector<int64_t>, std::greater<int64_t> >();
    for (int64_t i = 0; i < N - 1; ++i) {
        for (int64_t j = i + 1; j < N; ++j) {
            hq.push(A[i] * A[j]);
        }
    }

    int64_t ans = 0;
    for (int64_t i = 0; i < K; ++i) {
        ans = hq.top();
        // printf("%lld\n", ans);
        hq.pop();
    }
    printf("%lld\n", ans);
    return 0;
}

Submission status: Runtime Error

Solution code:
b = []
for i in range(len(a)):
    for j in range(i+1, len(a)):
        b.append(a[i]*a[j])
        print(" ".join([str(i),str(j)]))

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

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
import numpy as np


def test(a, K):
    from itertools import combinations
    answer = []
    for i, j in combinations(a, 2):
        answer.append(i * j)
    answer.sort()
    print(answer)
    print(answer[K - 1])


def main():
    read = sys.stdin.read

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

    # test(A, K)
    A.sort()
    m = bisect_left(A, 0)
    z = bisect_left(A, 1) - m
    p = N - m - z

    M = m * p
    Z = z * (N - z) + z * (z - 1) // 2
    negative = np.array(A[:m], np.int64)
    positive = np.array(A[-p:], np.int64)

    if K <= M:
        negative = -negative[::-1]
        left = 1
        right = -A[0] * A[-1] + 1
        while left + 1 < right:
            mid = (left + right) // 2
            cnt = (p - np.searchsorted(positive, (mid + negative - 1) // negative, side='left')).sum()
            if cnt < K:
                right = mid
            else:
                left = mid
        print(-left)
    elif K <= M + Z:
        print(0)
    else:
        print(CE)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

n,k = map(int,input().split())
a = [int(input()) for _ in range(n)]
pairs=[]
for i,x in enumerate(a):
    for y in a[i+1:]:
        pairs.append(x*y)
pairs.sort()
print(pairs[k-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

Nmax = int((N*(N-1))/2)
ans = [0] * Nmax

k = 0
step = 0

for i in range(N - 1):
    step = k + N - i - 1
    tmp = np.array(A[i+1:])
    ans[k:step] = A[i] * tmp
    k = step

ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np

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

Nmax = int((N*(N-1))/2)
ans = [0] * Nmax
tmp = [0] * (len(A) - 1)
k = 0
step = 0

for i in range(N - 1):
    step = k + N - i-1
    tmp = np.array(A[i+1:])
    ans[k:step] = A[i] * tmp
    k = step

ans.sort()
print(ans[K-1])

Submission status: Runtime Error

Solution code:
import numpy as np
stdin = open(0)
INF = 1145141919810893364
#INFはすくなくとも10^18+1は必要(10^9の積を扱うので)

N, K = map(int, stdin.readline().split())
A = np.array(stdin.read().split(), np.int64)

#まず、Aの要素を正、負、０に分ける
Posi = A[A>0]
Nega = A[A<0]
Nega2 = Nega*-1
Zero = A[A==0]
#Zeroの要素は0のみなのであえてvectorで持つ必要はないが、あえてこうしておく

#二分探索できるよう、ソートしておく
Posi = np.sort(Posi)
Nega = np.sort(Nega)
Nega2 = np.sort(Nega2)
Zero = np.sort(Zero)

#次に、N(N-1)/2個ある積のうち、正であるものの個数を求める
#負であるもの、０であるものも同様に求める

#積が正になるもの：ともに正かともに負
#積が負になるもの：正と負の組み合わせ
#積が０になるもの　どちらかが０
P_posi=0;P_nega=0;P_zero=0
P_posi += (len(Posi))*(len(Posi)-1)//2
P_posi += (len(Nega))*(len(Nega)-1)//2

P_nega += (len(Posi))*(len(Nega))

P_zero += (len(Zero))*(len(Zero)-1)//2
P_zero += (len(Zero))*(len(Posi))
P_zero += (len(Zero))*(len(Nega))

def main():
    
    #にぶたん開始
    l = -INF;r=INF;mid=0
    
    while abs(r-l)>1:
        mid=(l+r)//2
        #このにぶたんでは、mid未満の数はいくつあるかを数えたい
        #それは、後述する自作関数less_than()でO(NlogN)で計算できる
        num = less_than(mid);
        #mid未満の数はnum個である！
        
        #midより小さい数がK個と同じか少なかったらmidが小さすぎる
        if num<K:
            l=mid
        else:
            r=mid
    
    print(l)


#Xより少ない数はいくつある？
def less_than(X):
    R=0
    
    if X<0:
        #Xより小さい数はいくつ？？
        num=0
        for v in Nega:
            num += np.searchsorted(Posi, X//v, side='right')
        num = P_nega-num
        R=num
    
    elif X==0:
        R = P_nega
        
    else:
        #負の数をそのままにぶたんをするとこわれやすい(実装と頭が)
        #なので負の要素を全て正にしておいたもの(Nega2)を用意してそれでにぶたんをした
        
        #Xより小さい数はいくつ？？
        #まず０と負の数は明らかにXより小さい
        R+=P_nega+P_zero;
        #基本的には負の場合と同様の処理をする
        #しかし、正の場合はPosi*Posi,Nega*Negaなので重複をケアする必要がある
        #以下のように処理することでケアができる(図解すると理解が早い)
        num = 0
        for i in range(len(Posi)):
            temp = np.searchsorted(Posi, (X-1)//Posi[i], side='right')
            num += min(temp,i)
        for i in range(len(Nega2)):
            temp = np.searchsorted(Nega2, (X-1)//Nega2[i], side='right')
            num += min(temp,i)
        R += num
    return R

main()

Submission status: Runtime Error

Solution code:
#include <queue>
#include <vector>
#include <iostream>
#include <functional>

using namespace std;
using t=long long int;
int main() {
    int n, k;
    std::cin >> n >> k;
    
    vector<t> xs;
    t x;
    for (int i=0;i<n;++i){
        std::cin >> x;
        xs.push_back(x);
    }
    int len=xs.size();
    priority_queue<t, vector<t>, greater<t>> q;
    for (int i=0;i<len;++i){
        for (int j=0;j<i;++j){
            q.push(xs[i]*xs[j]);
        }
    }
    for (int i=0;i<k-1;++i)
        q.pop();
    cout<<q.top()<<endl;
}

Submission status: Runtime Error

Solution code:
N, K, *A = map(int, open(0).read().split())

neg = sorted([-a for a in A if a < 0])
pos = sorted([a for a in A if a >= 0])

def _count_pair_neg(x):
    x = -x
    res = 0

    MAX = len(neg)
    i = 0
    for n in reversed(neg):
        while i < MAX and n * pos[i] < x:
            i += 1
            
        res += len(pos) - i
    return res


def _count_pair_pos(x):
    res = 0

    # Negative list
    i = 0
    MAX = len(neg)
    for n in reversed(neg):
        if n * n <= x:
            res -= 1
            
        while i < MAX and neg[i] * n <= x:
            i += 1
        res += i
        
    # Positive list
    i = 0
    MAX = len(pos)
    for n in reversed(pos):
        if n * n <= x:
            res -= 1
            
        while i < MAX and pos[i] * n <= x:
            i += 1
        res += i
        
    # Devide by 2 for counting the same pair twice
    res //= 2
    res += len(neg) * len(pos)
    return res


def count_pair(x):
    if x < 0:
        return _count_pair_neg(x)
    
    return _count_pair_pos(x)


# Bounds
lb = 0
ub = 2 * 10 ** 18 + 2

while ub - lb > 1:
    mid = (ub + lb) // 2
    if count_pair(mid - 10 ** 18 - 1) < K:
        lb = mid
    else:
        ub = mid

print(ub - 10 ** 18 - 1)

Submission status: Runtime Error

Solution code:
import numpy as np

def check(num, input_list):
    multi_list = []
    input_list_np = np.array(input_list)
    
    multi_list_np = input_list_np * input_list_np.reshape(num, 1)
    multi_list = [multi_list_np[i,j] for i 
                  
if __name__ == '__main__':
    num, index = input().split()
    num = int(num)
    index = int(index)
    input_list = [int(a) for a in input().split()]

    print(check(num, input_list)[index - 1])

Submission status: Runtime Error

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

l_minus = [i for i in l if i < 0]
l_plus = [i for i in l if i > 0]
l_zero = [i for i in l if i == 0]
m_num = len(l_minus)
p_num = len(l_plus) 
z_num = len(l_zero) 

# 全部のペアの数
pairs_num = (n*(n-1))//2
# マイナスのペアの数はマイナスの数×プラスの数
m_pairs_num = m_num*p_num
# プラスのペアの数
p_pairs_num = ((m_num*(m_num-1))//2) + ((p_num*(p_num-1))//2)
# 0のペアの数
z_pairs_num = z_num*p_num + z_num*m_num + ((z_num*(z_num-1))//2)

# 0なら、0を出力して終了
if m_pairs_num < k and k < p_pairs_num:
    print (0)
    exit (0)

seki_list = []
# マイナスなら、マイナスのリストを作成して出力して終了
if k <= m_pairs_num:
    for i in l_minus:
        for j in l_plus:
            seki_list.append(i*j)
    print (sorted(seki_list)[k-1])
    exit (0)

# プラスなら、プラスのリストを作成して出力して終了
else:
    for i in range(m_num):
        for j in range(m_num):
                if i == j:
                    pass
                elif j < i:
                    pass
                else:
                    seki_list.append(l_minus[i]*l_minus[j])

    for i in range(p_num):
        for j in range(p_num):
                if i == j:
                    pass
                elif j < i:
                    pass
                else:
                    seki_list.append(l_plus[i]*l_plus[j])

    print (sorted(seki_list)[(k-1)-(m_pairs_num+z_pairs_num)])
    exit (0)