Novice D

Alice is able to determine what move Bob makes as Bob can only make one move to maximize the results.

Because Alice may choose only one entry of $$$A$$$, every other position has a fixed contribution we can precompute — specifically, how large the result would be if Bob chose that index after Alice's move. For any choice $$$i$$$ that Alice makes, Bob will pick whichever gives a larger value: either he picks $$$j = i$$$, or he picks the best index among all $$$j \neq i$$$. Alice's goal after that is to pick an index $$$i$$$ that minimizes this worse-case value.

To evaluate the best index among all $$$j \neq i$$$ efficiently for every i, we can compute the two largest values of $$$f(j) = A_j | (y-A_j)$$$ over all $$$j$$$. For a given index $$$i$$$, if the overall maximum $$$f(j)$$$ comes from $$$j = i$$$, then the best choice among the remaining indices is the second-largest. Otherwise, the best choice is the largest. Using this idea, we can check every $$$i$$$ in constant time after the initial scan, giving an $$$O(n)$$$ solution.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main(){
    cin.tie(0)->sync_with_stdio(0);
 
    int t;
    cin >> t;
    
    while(t--){
        int n; ll x, y;
        cin >> n >> x >> y;
        
        vector<ll> vals(n);
        ll sum = 0;
        for(int i = 0; i < n; ++i) {
            cin >> vals[i];
            sum += vals[i];
        }
 
        vector<ll> loss(n);
        for(int i = 0; i < n; ++i) loss[i] = vals[i]-(vals[i]&y);
 
        ll min1 = LLONG_MAX, min2 = LLONG_MAX;
        int idx1 = -1;
        for(int i = 0; i < n; ++i) {
            if(loss[i] < min1){
                min2 = min1;
                min1 = loss[i];
                idx1 = i;
            } else if(loss[i] < min2) {
                min2 = loss[i];
            }
        }
 
        ll ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            ll alice = vals[i]|x;
            ll delta = alice-vals[i], same = alice-(alice&y);
            ll obest = ((i == idx1) ? min2 : min1);
            ll bob = min(obest, same);
            ll temp = sum+delta-bob;
            ans = min(ans, temp);
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}