Language: C++


#include <bits/stdc++.h>

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const LL inf = 1LL<<60;
LL n,k; vector<LL> neg,zero,pos, A;

LL count(const LL mid)
{
    LL cnt = 0;
    if (mid < 0) {
        for (int i = 0; i < neg.size(); i++) {
            const LL  x = ceil(1.0*mid/neg[i]);
            const int j = lower_bound(ALL(pos),x) - pos.begin();
            cnt += pos.size() - j;
        }
    }
    if (mid == 0) {
        cnt += 1LL * neg.size() * pos.size();
        cnt += 1LL * neg.size() * zero.size();
        cnt += 1LL * pos.size() * zero.size();
        cnt += 1LL * zero.size() * (zero.size()-1)/2;
    }
    if (mid > 0) {
        cnt += 1LL * neg.size() * pos.size();
        cnt += 1LL * neg.size() * zero.size();
        cnt += 1LL * pos.size() * zero.size();
        cnt += 1LL * zero.size() * (zero.size()-1)/2;
        for (int i = 0; i < neg.size(); i++) {
            const LL  x = mid/neg[i];
            const int j = lower_bound(
                neg.begin()+i+1, neg.end(), x) - neg.begin();
            cnt += neg.size() - j;
        }
        for (int i = 0; i < pos.size(); i++) {
            const LL  x = mid/pos[i];
            const int j = upper_bound(
                pos.begin()+i+1, pos.end(), x) - pos.begin();
            cnt += j - (i+1);
        }
    }
    return cnt;
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    while (cin >> n >> k) {
        neg.clear(); zero.clear(); pos.clear(); A.clear();
        FOR(i,0,n) {
            LL a; cin >> a;
            A.push_back(a);
            if (a <  0) neg. push_back(a);
            if (a == 0) zero.push_back(a);
            if (a >  0) pos. push_back(a);
        }
        sort(ALL(neg)); sort(ALL(pos)); sort(ALL(A));
        LL lo = -inf, hi = inf;
        while (lo < hi) {
            const LL mid = lo + (hi-lo)/2;
            if (count(mid) >= k)
                hi = mid;
            else
                lo = mid + 1;
        }
        LL ans = lo; 
        if (ans == 0 && lower_bound(ALL(A),0) != A.end())
            ;
        else {
            LL res = inf;
            if (ans < 0) {
                FOR_ALL(a,neg) {
                    const LL b = ans / *a;
                    const int j = upper_bound(ALL(pos),b) - pos.begin();
                    if (pos.size() > 1 && j) {
                        const LL x = *a * pos[j-1];
                        res = min(res, x);
                    }
                }
                if (neg.size() >= 2) {
                    const LL a = neg[neg.size()-1];
                    const LL b = neg[neg.size()-2];
                    res = min(res, a*b);
                }
                if (pos.size() >= 2) {
                    const LL a = pos[0];
                    const LL b = pos[1];
                    res = min(res, a*b);
                }
                if (zero.size())
                    res = min(res, 0);
            }
            else {
                FOR(i,0,neg.size()) {
                    const LL b = floor(1.0*ans / neg[i]);
                    int j = lower_bound(ALL(neg),b) - neg.begin();
                    if (neg[j] > b)
                        j--;
                    if (j == i)
                        j--;
                    if (0 <= j)
                        res = min(res, neg[i]*neg[j]);
                }
                FOR(i,0,pos.size()) {
                    const LL b = ceil(1.0*ans / pos[i]);
                    int j = lower_bound(ALL(pos),b) - pos.begin();
                    if (j == i)
                        j++;
                    if (j < pos.size())
                        res = min(res, pos[i]*pos[j]);
                }
            }
            ans = res;
        }
        cout << ans << endl;
    }
    return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:129:30: error: no matching function for call to 'min(LL&, int)'
  129 |                     res = min(res, 0);
      |                           ~~~^~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:2:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:129:30: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  129 |                     res = min(res, 0);
      |                           ~~~^~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:129:30: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  129 |                     res = min(res, 0);
      |                           ~~~^~~~~~~~