Find Pair

题意翻译

# 题目描述 你又遇到了一道关于排列的问题。 首先，考虑一个包含 _n_ 个整数的数列 _a₁_ , _a₂_ ... _aₙ_ (不一定互不相同)。你发现由其中任意两项组成的数对 (aᵢ, aⱼ)(1 <= i, j <= n)十分有趣，于是你想探究给定数列中所有 _n²_ 组数对的规律。 例如，数列{3, 1, 5}能组成九组数对： (3, 3), (3, 1), (3, 5), (1, 3), (1, 1), (1, 5), (5, 3), (5, 1), (5, 5)。 接下来，将这些数对按照字典序升序排列。比如，两组数对(_p₁_, _p₂_)，(_q₁_, _q₂_)，当且仅当 _p₁_ < _p₂_，或 _p₁_ = _p₂_ 且 _q₁_ < _q₂_ 时，我们说(_p₁_, _p₂_)的字典序小于(_q₁_, _q₂_)的字典序。 于是，上述数列组成的数对排序后将成为： (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)。 将排好序的数组标上按顺序编号为 1 ～ _n²_ 。现在，你想要知道其中第 _k_ 组数对是什么。 # 输入输出格式 ## 输入格式 第一行包括两个整数 _n_ 和 _k_ (1 <= _n_ <= 10⁵，1 <= _k_ <= _n²_ )。 第二行包括 _n_ 个整数 _a₁_ , _a₂_ ... _aₙ_ (-10⁹ <= aᵢ <= 10⁹)，表示数列的每一项，数值可以重复。每一项之间由一个空格隔开。 注意，C++中不建议使用格式控制符 %lld 读写64位长整型数据，最好使用 cin，cout，streams 或 %I64d 格式控制符。 ## 输出格式 只有一行，包括两个数字，表示排好序的 _n²_ 个数对的第 _k_ 组。 # 说明 样例 #1 中排好序的数对为： (1, 1), (1, 2), (2, 1), (2, 2) 所以第4项为(2, 2)。 样例 #2 中排好序的数对为： (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5) 所以第2项为(1, 3)。

题目描述

You've got another problem dealing with arrays. Let's consider an arbitrary sequence containing $ n $ (not necessarily different) integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ . We are interested in all possible pairs of numbers ( $ a_{i} $ , $ a_{j} $ ), ( $ 1<=i,j<=n $ ). In other words, let's consider all $ n^{2} $ pairs of numbers, picked from the given array. For example, in sequence $ a={3,1,5} $ are $ 9 $ pairs of numbers: $ (3,3),(3,1),(3,5),(1,3),(1,1),(1,5),(5,3),(5,1),(5,5) $ . Let's sort all resulting pairs lexicographically by non-decreasing. Let us remind you that pair ( $ p_{1} $ , $ q_{1} $ ) is lexicographically less than pair ( $ p_{2} $ , $ q_{2} $ ) only if either $ p_{1} $ < $ p_{2} $ , or $ p_{1} $ = $ p_{2} $ and $ q_{1} $ < $ q_{2} $ . Then the sequence, mentioned above, will be sorted like that: $ (1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5) $ Let's number all the pair in the sorted list from $ 1 $ to $ n^{2} $ . Your task is formulated like this: you should find the $ k $ -th pair in the ordered list of all possible pairs of the array you've been given.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=10^{5},1<=k<=n^{2} $ ). The second line contains the array containing $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ). The numbers in the array can coincide. All numbers are separated with spaces. Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout, streams or the %I64d specificator instead.

输出格式

In the single line print two numbers — the sought $ k $ -th pair.

输入输出样例

输入样例 #1

2 4
2 1

输出样例 #1

2 2

输入样例 #2

3 2
3 1 5

输出样例 #2

1 3

说明

In the first sample the sorted sequence for the given array looks as: $ (1,1),(1,2),(2,1),(2,2) $ . The $ 4 $ -th of them is pair $ (2,2) $ . The sorted sequence for the array from the second sample is given in the statement. The $ 2 $ -nd pair there is $ (1,3) $ .

题意翻译

# 题目描述 你又遇到了一道关于排列的问题。 首先，考虑一个包含 _n_ 个整数的数列 _a₁_ , _a₂_ ... _aₙ_ (不一定互不相同)。你发现由其中任意两项组成的数对 (aᵢ, aⱼ)(1 <= i, j <= n)十分有趣，于是你想探究给定数列中所有 _n²_ 组数对的规律。 例如，数列{3, 1, 5}能组成九组数对： (3, 3), (3, 1), (3, 5), (1, 3), (1, 1), (1, 5), (5, 3), (5, 1), (5, 5)。 接下来，将这些数对按照字典序升序排列。比如，两组数对(_p₁_, _p₂_)，(_q₁_, _q₂_)，当且仅当 _p₁_ < _p₂_，或 _p₁_ = _p₂_ 且 _q₁_ < _q₂_ 时，我们说(_p₁_, _p₂_)的字典序小于(_q₁_, _q₂_)的字典序。 于是，上述数列组成的数对排序后将成为： (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5)。 将排好序的数组标上按顺序编号为 1 ～ _n²_ 。现在，你想要知道其中第 _k_ 组数对是什么。 # 输入输出格式 ## 输入格式 第一行包括两个整数 _n_ 和 _k_ (1 <= _n_ <= 10⁵，1 <= _k_ <= _n²_ )。 第二行包括 _n_ 个整数 _a₁_ , _a₂_ ... _aₙ_ (-10⁹ <= aᵢ <= 10⁹)，表示数列的每一项，数值可以重复。每一项之间由一个空格隔开。 注意，C++中不建议使用格式控制符 %lld 读写64位长整型数据，最好使用 cin，cout，streams 或 %I64d 格式控制符。 ## 输出格式 只有一行，包括两个数字，表示排好序的 _n²_ 个数对的第 _k_ 组。 # 说明 样例 #1 中排好序的数对为： (1, 1), (1, 2), (2, 1), (2, 2) 所以第4项为(2, 2)。 样例 #2 中排好序的数对为： (1, 1), (1, 3), (1, 5), (3, 1), (3, 3), (3, 5), (5, 1), (5, 3), (5, 5) 所以第2项为(1, 3)。