CodeForces 160C Find Pair（思维）

朱雀 2022-06-03 05:43 159阅读 0赞

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.

Input

The first line contains two integers *n* and *k* (1 ≤ *n* ≤ 105, 1 ≤ *k* ≤ *n*2). The second line contains the array containing *n* integers *a*1, *a*2, ..., *a**n* ( - 109 ≤ *a**i* ≤ 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

Note

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).

题解：

如果这题没重复数据可以发现先从小到大sort一下，第一个数字为第(k%n==0)?k/n-1:k/n 这个式子算出的下标，第二个会是(k-1+n)%n的下标

第一次直接用取模找的规律到第3组就wa了，仔细想想发现当输入数据有重复的时候找规律直接输出会出错，这个时候要特殊处理一遍

可以发现用取模的方法得到的第一个数字一定是对的，那么我就用num记录数组中和算出的第一个数字相同的个数，用st记录下算出的第一个数字的前一个不同种数字的位置，

这么做是有原因的，因为一直到st前面的排序都是对的，那么我们就把k处理一下，后面的由于算出的第一个数字在数组中有相同的时候会有些pair后面的那个数字更小但是后算出来，这样是错的，这个时候要对后面进行重新排序，pair第一个数字设算出的为x，在数组中的数目为num，那么对于数组中的每一个数字都应该放num个，这样的话同样用取模的方法很快可以算出第二个的下标。。这个不太好说要体会一下，还有就是有些特殊情况要特判

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    ll a[100005];
    map<ll,ll>p;
    int main()
    {
        ll n,k,i,j,temp;
        scanf("%I64d%I64d",&n,&k);
        for(i=0;i<n;i++)
        {
            scanf("%I64d",&a[i]);
            p[a[i]]=p[a[i]]+1;
        }
        temp=k;
        sort(a,a+n);
        int t=(k%n==0)?k/n-1:k/n;
        printf("%I64d",a[t]);
        int num=1,ans;
        int st=t;
        for(i=t-1;i>=0;i--)
        {
            if(a[i]==a[i+1])
            {
                st=i;
            }
            else
                break;
        }
        k-=(st)*n;
        for(i=st+1;i<n;i++)
        {
            if(a[i]==a[i-1])
            {
                num++;
            }
            else
                break;
        }
        if(num==1)
        {
            printf(" %I64d\n",a[(temp-1+n)%n]);
        }
        else
            printf(" %I64d\n",a[k%num==0?k/num-1:k/num]);
        return 0;
    }