在线等help
查看原帖
在线等help
1010570
违规用户名1010570楼主2024/9/26 17:09
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,cnt;
vector<int> x,y;
bool check(int mid){
    int to=0;
    if(mid<0){
        for(int i=0;i<x.size();i++){
            int now=mid/x[i];
            if(mid%x[i]==0){
                now--;
            }
            to+=upper_bound(y.begin(),y.end(),now)-y.begin();
        }
    }
    else if(mid==0){
        to+=x.size()*y.size();
    }
    else{
        to+=x.size()*y.size();
        to+=cnt*(x.size()+y.size());
        to+=cnt*(cnt-1)/2;
        for(int i=0;i<x.size();i++){
            int now=mid/x[i];
            if(mid%x[i]==0){
                now--;
            }
            int pos=upper_bound(x.begin(),x.end(),now)-x.begin();
            if(pos>i){
                to+=pos-i-1;
            }
        }
        for(int i=0;i<y.size();i++){
            int now=mid/y[i];
            if(mid%y[i]==0){
                now--;
            }
            int pos=upper_bound(y.begin(),y.end(),now)-y.begin();
            if(pos>i){
                to+=pos-i-1;
            }
        }
    }
    return to<=k-1;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        if(a>0){
            x.push_back(a);
        }
        else if(a<0){
            y.push_back(a);
        }
        else{
            cnt++;
        }
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    int l=(int)(-1e18),r=(int)(1e18),ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans;
}
2024/9/26 17:09
加载中...