Haidora or not Haidora? (Çözgüdiň düşündirişi)

Solution

We want to maximise the value of

after choosing exactly $k$ distinct indices and replacing each chosen a_i by its $32$-bit bitwise NOT \sim a_i. Since $\sim$ is taken over $32$ bits, we can think of it as \sim x = (2^{32}-1) - x, or equivalently \sim x = (\texttt{MASK} \,\hat{}\, x) with \texttt{MASK} = 2^{32}-1.

Let the final answer be $X$. For every bit that is $1$ in $X$, every element in the final array must also have that bit equal to $1$, otherwise the AND would have $0$ in that position. This suggests constructing $X$ greedily bit by bit from the most significant bit to the least significant bit: we maintain a current answer ans, and for each bit $j$ from $31$ down to $0$ we try to set it to $1$ on top of what we already fixed.

Concretely, at bit $j$ we form a candidate value

meaning we want the final AND to have all bits that are $1$ in cand. For this fixed cand, we run a feasibility check on the whole array. For each element x = a_i there are only two states in the final configuration: either we keep it as $x$, or we flip it to y = \sim x = (\texttt{MASK} - x). For cand to be achievable, for each position $i$ at least one of these options must fully cover all bits of cand:

Looking at (\text{keep\_ok}, \text{flip\_ok}) we split indices into three useful types:

• If both are false, neither $x$ nor $\sim x$ has all bits of cand, so this index can never satisfy cand. Then cand itself is impossible and we must reject this bit.

• If \text{keep\_ok} = \text{false} and \text{flip\_ok} = \text{true}, we are forced to flip this index to satisfy cand. Let $F$ be the number of such forced indices.

• If \text{keep\_ok} = \text{true} and \text{flip\_ok} = \text{true}, this index is flexible: both keeping and flipping still satisfy cand. Let $C$ be the number of such flexible indices.

(When \text{keep\_ok} = \text{true} and \text{flip\_ok} = \text{false} we simply must keep the element; it consumes no flip and gives no flexibility.)

We must perform exactly $k$ flips overall. For a fixed cand, all $F$ forced indices must be flipped, so we need at least $F$ flips. On the other hand, we can optionally flip any subset of the $C$ flexible indices, so the total number of flips we can realise while still satisfying cand ranges from $F$ (only forced ones) up to F+C (forced ones plus all flexible ones). Hence cand is feasible if and only if

If this inequality holds, we know there exists a way to choose exactly $k$ indices to flip so that every final element covers all bits of cand. In that case we accept this bit and set \texttt{ans} := \texttt{cand}. If not, we leave the bit at $0$ in ans and move on to the next lower bit.

Because we process bits from the most significant downwards and only set a bit when there exists some configuration of exactly $k$ flips that supports all bits chosen so far, the resulting ans is the lexicographically (and thus numerically) maximum final AND attainable. For each of the $32$ bit positions we scan all $n$ elements once, so the overall complexity is O(32n) = O(n) in time and $O(1)$ extra memory besides the input array.

n,k=map(int, input().split())
a=list(map(int, input().split()))

MASK=(1<<32)-1
ans=0

for j in range(31, -1, -1):
    p=1<<j
    cand = ans | p
    forced = 0
    flex = 0
    ok = True
    for x in a:
        keep = (x & cand) == cand
        flipped = (~x) & MASK     
        flip = (flipped & cand) == cand

        if not keep and not flip:
            ok = False
            break
        if not keep and flip:
            forced += 1       
        elif keep and flip:
            flex += 1         

    if not ok:
        continue

    rem = k - forced
    if rem < 0 or rem > flex:
        continue

    ans = cand

print(ans)