牛客练习赛135 E

晕了晕了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
#define int long long
const int N=2e5+10;
ll a[N];
int t,n;
ll y;
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n>>y;
        ll sum=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        if(sum>=y){
            cout<<0<<endl;
            continue;
        }
        ll ans=1e18;
        for(int i=0;i<=65;i++){
            vector<int> v;
            ll sum_all=0;
            ll sum_sub=sum;
            for(int j=1;j<=n;j++){
                if(((a[j]>>i)&1)==0){
                    v.push_back(j);
                    sum_all+=a[j];
                }
            }
            sum_sub-=sum_all;
            int len=v.size();
            int j=i;
            ll num=0;
            while(j>=0){
                int cnt=0;//0的个数
                for(auto x:v){
                    if(((a[x]>>j)&1)==0) cnt++;
                }
                if(cnt>len-cnt){
                    sum_all-=(1<<j)*(len-cnt);
                    sum_all+=(1<<j)*cnt;
                    num+=(1<<j);//放1
                }
                j--;
            }
            if(sum_all+sum_sub<y) continue;
            ans=min(ans,num);
            j=i;
            while(j>=0){
                int cnt=0;//0的个数
                for(auto x:v){
                    if(((a[x]>>j)&1)==0) cnt++;
                }
                if(cnt>len-cnt){//0多
                    ll s=sum_all;
                    s-=(1<<j)*cnt;
                    s+=(1<<j)*(len-cnt);
                    ll num1=num;
                    num1=num1-(1<<j);
                    if(s+sum_sub>=y){
                        ans=min(ans,num1);
                        sum_all=s;
                        num=num1;
                    }
                }
                j--;
            }
            break;
        }
        cout<<ans<<endl;
    }
    return 0;
}