Codeforces 160C(脑洞)-蒲公英云

Codeforces 160C(脑洞)

青旅半醒 2022-06-03 06:43 327阅读 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;
 }