CF160C.Find Pair
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You've got another problem dealing with arrays. Let's consider an arbitrary sequence containing n (not necessarily different) integers a1 , a2 , ..., an . We are interested in all possible pairs of numbers ( ai , aj ), ( 1<=i,j<=n ). In other words, let's consider all n2 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 ( p1 , q1 ) is lexicographically less than pair ( p2 , q2 ) only if either p1 < p2 , or p1 = p2 and q1 < q2 .
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 n2 . 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<=105,1<=k<=n2 ). The second line contains the array containing n integers a1 , a2 , ..., an ( −109<=ai<=109 ). 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) .