Overview

Given \(N\) candidates, the problem asks for the maximum number of people you can select such that the bitwise OR of all selected members’ skill values equals exactly the target value \(K\).

Analysis

Key Observation ①: Filtering Candidates

A fundamental property of the bitwise OR operation is that once a bit is set, it never goes away. In other words, if a candidate \(i\)’s skill value \(A_i\) contains a bit that is not set in \(K\), then including that candidate in the team would cause an extra bit to appear in the team’s overall OR, making the OR exceed \(K\).

Therefore, the only candidates eligible for the team are those where \(A_i\) is a submask of \(K\), i.e., those satisfying \(A_i \mathbin{\&} K = A_i\) (or equivalently, \(A_i \mathbin{|} K = K\)).

Key Observation ②: To Maximize the Number of People, Include Everyone

Candidates satisfying the condition (those that are submasks) will never add any extra bits to the OR no matter which ones you select. Therefore, it is perfectly fine to include all valid candidates in the team. In fact, since we want to maximize the number of people, including all of them is optimal.

However, we need to verify that the OR of all included candidates equals exactly \(K\). If the OR falls short of \(K\) (i.e., there is no candidate covering some bit of \(K\)), then no valid answer exists.

Why a Brute-Force Approach Is Unnecessary

Enumerating all \(2^N\) subsets is completely infeasible since \(N\) can be up to \(2 \times 10^5\). However, thanks to the above observations, the problem can be solved greedily by simply including everyone who qualifies, so enumeration is unnecessary.

Algorithm

1. For each candidate \(A_i\), check whether \(A_i \mathbin{\&} K = A_i\) holds, and collect only those that satisfy this condition (the valid list).
2. If valid is empty, the answer is \(-1\).
3. Compute the OR of all elements in valid.
4. If that OR equals exactly \(K\), the answer is the number of elements in valid (= selecting everyone). Otherwise, the answer is \(-1\).

Concrete Example

For \(N = 4, K = 7 \;(= 111_2)\), \(A = [3, 5, 8, 6]\):

• \(3 = 011_2\): \(3 \mathbin{\&} 7 = 3\) ✔️ (submask)
• \(5 = 101_2\): \(5 \mathbin{\&} 7 = 5\) ✔️
• \(8 = 1000_2\): \(8 \mathbin{\&} 7 = 0 \neq 8\) ❌ (has a bit not present in \(K\))
• \(6 = 110_2\): \(6 \mathbin{\&} 7 = 6\) ✔️

valid = [3, 5, 6], overall OR \(= 3 \mathbin{|} 5 \mathbin{|} 6 = 7 = K\) ✔️

The answer is \(3\) people.

Complexity

• Time complexity: \(O(N)\) (just checking each candidate once and computing the OR)
• Space complexity: \(O(N)\) (for storing the valid list)

Implementation Notes

• Although \(K\) and \(A_i\) can be as large as \(10^{18}\), Python natively handles arbitrary-precision integers, so no special treatment is needed.

• The submask check can be done in a single line: (a & K) == a.

• Since the input can be large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # A candidate can be in the team only if A_i is a submask of K (i.e., A_i | K == K, equivalently A_i & K == A_i)
    # We need to select a non-empty subset of such candidates whose OR is exactly K.
    
    # Step 1: Filter candidates whose A_i is a submask of K
    valid = [a for a in A if (a & K) == a]
    
    if not valid:
        print(-1)
        return
    
    # Step 2: Check if OR of all valid candidates equals K
    total_or = 0
    for a in valid:
        total_or |= a
    
    if total_or != K:
        print(-1)
        return
    
    # Step 3: All valid candidates can be included! Because each valid candidate is a submask of K,
    # and together they OR to K. So the answer is len(valid).
    # Wait, that's correct: every valid candidate has A_i & K == A_i, so including all of them
    # gives OR = total_or = K. We want maximum number, so include all valid candidates.
    
    print(len(valid))

main()

---

This editorial was generated by claude4.6opus-thinking.