Codeforces 160C(脑洞)

青旅半醒 2022-06-03 06:43 206阅读 0赞

问题描述:

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.

Input

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.

Output

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

Example

Input

2 4
    2 1

Output

2 2

Input

3 2
    3 1 5

Output

1 3

题目题意:给我们n个数，形成n\*n个数对，按照字典序排序后第k个数是哪一个数对

题目分析:这道题目的关键是如果俩个数相等的时候，怎么去找，所以我们需要记录一下每一个数出现的个数，通过k的值我们可以找到第一个数，如果第一个数的个数不止一个，我们就需要（举个例子）

1 1 3   k为5

首先k/3+1等于2那么为1，但是1的个数有俩个，我们需要以俩个俩个的来找，因为（1，1） （1，1）一定是这样往下面排的

代码如下:

#include<iostream>
     #include<cstdio>
     #include<cmath>
     #include<cstring>
     #include<algorithm>
     #define ll long long
     using namespace std;
    
     const int maxn=1e5+100;
     ll a[maxn],num[maxn];
    
     int main()
     {
         ll n,k;
         while (scanf("%lld%lld",&n,&k)!=EOF) {
            for (int i=1;i<=n;i++) {
                scanf("%lld",&a[i]);
            }
            sort (a+1,a+n+1);
            for (int i=1;i<=n;i++) {
                ll sum=0;
                for (int j=i;j<=n;j++) {
                    if (a[i]==a[j]) sum++;
                    else break;
                }
                for (int j=i;j<=i+sum;j++) num[j]=sum;
                i=i+sum-1;
            }
            ll pos;
            if (k%n==0) pos=k/n;
            else pos=k/n+1;
            if (num[pos]==1) {
                ll res=k-(pos-1)*n;
                printf("%lld %lld\n",a[pos],a[res]);
            }
            else {
                while (num[pos]==num[pos-1]&&a[pos]==a[pos-1]) pos=pos-1;
                ll res=k-(pos-1)*n;
                if (res%num[pos]==0) {
                    printf("%lld %lld\n",a[pos],a[res/num[pos]]);
    
                }
                else {
                int cnt=1;
                while (res-cnt*num[pos]>=0) cnt++;
                printf("%lld %lld",a[pos],a[cnt]);
                }
            }
         }
         return 0;
     }