两数之积(Product of Two)

题目描述

给定 $n$ 个整数的序列 $a_1,a_2,\cdots,a_n$，将任意两个整数相乘得到新序列（共 $\frac{n(n-1)}{2}$ 个数），求新序列从大到小排序后第 $t$ 大的数字。

输入格式

输入共两行：

• 第一行：两个正整数 $n,t$
• 第二行：$n$ 个整数 $a_1,a_2,\ldots,a_n$

输出格式

输出共一行，一个整数表示所有两数乘积中第 $t$ 大的数字。

样例输入 #1

4 5
7 -2 8 4

样例输出 #1

-14

说明：两两乘积共 $-14,56,28,-16,-8,32$，第 $5$ 大为 $-14$

数据范围

• 对于 $30\%$ 的数据，$n\leq 500$
• 对于另外 $40\%$ 的数据，$1\leq a_i\leq 2\times10^9$
• 对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$-2\times10^9\leq a_i\leq 2\times10^9$，$1\leq t\leq\frac{n(n-1)}{2}$

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布