Language: C++

#include <iostream>
#include <vector>
#include <climits>
#include <set>

using namespace std;

typedef long long ll;
ll N,K;

int main() {
    cin >> N >> K;
    K--;
    vector<ll> A(N);
    vector<ll> A_pos;
    vector<ll> A_neg;
    ll A_zero = 0;
    for(int i = 0; i < N; i++) { cin >> A[i];}
    sort(A.begin(),A.end());
    for(const auto a: A) {
        if(a == 0) {A_zero ++;}
        if(a < 0) {A_neg.push_back(a);}
        if(a > 0) {A_pos.push_back(a);}
    }

    // find the largest value s.t. the number of values less than v is <= K or equal
    if(N == 1) { cout << A[0] << endl; return 0 ;}

    ll ans = min(A[0]*A[1], A[N-1]*A[0]);
    ll jump = max(A[0]*A[1], A[N-1]*A[N-2]);
    ans = -jump;
    // cout << "start ans start jump " << ans << " " << jump << endl;

    auto ok = [&](ll value) {
        // cout << "Checking " << value << endl;

        //ll num_less_ = 0;
        //for(int i = 0; i < N; i++) {
        //    for(int j = i+1; j < N; j++) {
        //        if(A[i]*A[j]<value) num_less_++;
        //    }
        //}
        ll num_less = 0;
        for(int i = 0; i < N; i++) {
            ll num_less_this = 0;
            if(A[i] < 0) {
                if(value < 0) {
                    // number of positive larger
                    ll idx = A_pos.size();
                    ll jump = A_pos.size();
                    while(jump > 0) {
                        while(idx-jump >= 0 && A[i]*A_pos[idx-jump] < value) {
                            idx -= jump;
                        }
                        jump /= 2;
                    }
                    num_less_this = A_pos.size()-idx;
                } 
                else if(value == 0) {
                    // number of positive values 
                    num_less_this = A_pos.size();
                } 
                else if (value > 0) {
                    // All non negative numbers + number of negatives (starting from largest)
                    num_less_this += A_zero + A_pos.size();
                    ll idx = A_neg.size();
                    ll jump = A_neg.size();
                    while (jump > 0) {
                        while(idx-jump >= 0 && A[i]*A_neg[idx-jump] < value) {
                            idx -= jump;
                        }
                        jump /= 2;
                    }
                    num_less_this += A_neg.size()-idx;
                }
            } 
            else if(A[i] > 0) {
                if(value < 0) {
                    ll idx = -1;
                    ll jump = A_neg.size();
                    while(jump > 0) {
                        while(idx+jump < A_neg.size() && A[i]*A_neg[idx+jump] < value) {
                            idx += jump;
                        }
                        jump/=2;
                    }
                    num_less_this += idx+1;
                }
                else if(value == 0) {
                    num_less_this += A_neg.size();
                } 
                else if(value > 0) {
                    // number of 0 and negative numbers
                    num_less_this += A_neg.size() + A_zero;
                    // number of positive values small enough
                    ll idx = -1;
                    ll jump = A_pos.size();
                    while(jump > 0) {
                        while(idx+jump < A_pos.size() && A[i]*A_pos[idx+jump] < value) {
                            idx += jump;
                        }
                        jump /= 2;
                    }
                    //cout << "contributed from positive " << idx+1 << endl;
                    num_less_this += idx+1;
                }
            }
            else if(A[i] == 0) {
                if(value > 0) {
                    num_less_this += N;
                }
            }
            if(A[i]*A[i] < value) { num_less_this --;}

//            ll num_less_this_ = 0;
//            for(int j = 0; j < N; j++) {
//                if (i != j && A[i]*A[j] < value) { num_less_this_++;}
//            }
//             cout << "num_less_this after processing idx=" << i << " A[i]=" << A[i] << " is "  << num_less_this << endl;
//             cout << "num_less_this TRUE after processing idx=" << i << " A[i]=" << A[i] << " is "  << num_less_this_ << endl;
//
            num_less += num_less_this;
        }
        num_less /= 2;

//        cout << "Number of things less " << value << " is " << num_less << endl;
//        cout << "TRUE: Number of things less " << value << " is " << num_less_ << endl;
        return num_less <= K;
    };


    while(jump > 0) {
        while(ok(ans+jump)) {
            ans += jump;
        }
        jump /= 2;
    }

    cout << ans << endl;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:19:5: error: 'sort' was not declared in this scope; did you mean 'short'?
   19 |     sort(A.begin(),A.end());
      |     ^~~~
      |     short