Overview

Given \(N\) candidates, select a subset such that the bitwise OR of each person’s skill value is exactly \(K\), and maximize the number of people selected.

Analysis

The key to this problem is utilizing the properties of the bitwise OR operation. In bitwise OR, once a bit becomes 1, it stays 1 forever. Therefore, the condition “the final OR equals \(K\)” can be rephrased as follows:

1. No one’s bits should exceed the bits of \(K\) (i.e., OR > K must not happen) 　→ Candidates who have a 1 in a position where \(K\)’s bit is 0 must be excluded.

2. For each position where \(K\)’s bit is 1, at least one person must have that bit

Therefore, we consider the following steps:

Step 1: Exclude invalid candidates

Candidates who have a 1 in a position where \(K\)’s bit is 0 must be excluded, since using them would cause the OR to exceed \(K\).

Step 2: Cover all required bits

For each position where \(K\)’s bit is 1, there must be at least one candidate who covers it. If no such candidate exists for any required bit, the answer is \(-1\).

Step 3: Select the maximum number of people

Among the candidates satisfying the above conditions, we need to select as many people as possible. However, we must ensure that selecting everyone does not cause the OR to exceed \(K\).

In fact, selecting all candidates who satisfy condition 1 will never cause the OR to exceed \(K\) (because no one has any forbidden bits). Therefore, the problem reduces to “ensure the required bits are covered, and select everyone else as well.”

The key point here is greedily selecting the minimum number of people to cover each required bit. Specifically, if multiple candidates cover a given bit, there is no need to avoid overlap.

In practice, it is sufficient to assign at least one person to each bit, and all other people can be selected as well.

Therefore, the problem can be solved as follows: 1. Extract candidates who do not violate condition 1 2. Check whether each required bit is covered by someone 3. Since we can select all of them, output the number of candidates directly

An initial misconception was attempting to strictly compute the “minimum cover set,” but in this case, selecting everyone is valid, so that is unnecessary.

Algorithm

1. Read the input.
2. Exclude candidates who have a 1 in a position where \(K\)’s bit is 0.
3. Among the remaining candidates, check whether each bit of \(K\) (those that are 1) is covered by someone.
4. If all bits are covered, all remaining candidates can be selected, so output their count.
5. Otherwise, output \(-1\).

Complexity

• Time complexity: \(O(N \log K)\) (bit operations and candidate filtering)
• Space complexity: \(O(N)\)

Implementation Notes

• Candidates who have a 1 in a position where \(K\)’s bit is 0 must never be selected
• Check whether each required bit (bits that are 1 in \(K\)) is held by someone
• Ultimately, all valid candidates can be used, so simply output their count

## Source Code

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # スキル値のビット位置を管理する
    # Kのビットが立っている位置について、少なくとも1人はそのビットを持っていなければならない
    # Kのビットが立っていない位置については、誰もそのビットを持っていてはいけない

    # まず、Kのビットが立っていない位置に1を持つ候補者は除外する
    # なぜなら、それがあると OR が K を超えてしまうため
    max_bit = 60  # 10^18 < 2^60
    mask = (1 << max_bit) - 1  # 全ビットが1のマスク
    forbidden_mask = (~K) & mask  # Kで0になっているビットの位置

    valid_candidates = []
    for a in A:
        if a & forbidden_mask:
            continue
        valid_candidates.append(a)

    if not valid_candidates:
        print(-1)
        return

    # 次に、Kのビットが立っている位置について、それぞれをカバーする候補者がいるか確認
    required_bits = []
    for i in range(max_bit):
        if K & (1 << i):
            required_bits.append(i)

    # 各required bitをカバーする候補者のリスト
    covered_by = [[] for _ in range(len(required_bits))]
    for idx, a in enumerate(valid_candidates):
        for i, bit_pos in enumerate(required_bits):
            if a & (1 << bit_pos):
                covered_by[i].append(idx)

    # それぞれのビットをカバーする候補者がいなければ-1
    for cover_list in covered_by:
        if not cover_list:
            print(-1)
            return

    # 貪欲法: 最大人数を選ぶために、できるだけ多くの人を選んで、最終的にORがKになるか確認
    # すべてのrequired bitsがカバーされている範囲で、最大の部分集合を選ぶ
    # これは貪欲に、各required bitに対して1人だけ割り当て、残りは自由に追加できると考える

    # 実際には、ORがKになる最大の部分集合を効率的に見つける必要がある
    # 方法: 必要最小限の候補者を選んで各required bitをカバーし、その後、他の候補者を追加してもORがKを超えないようにする

    # 必須の候補者を決める: 各required bitについて1人ずつ担当させる（被り可）
    # この担当者たちを含む最大集合を構築する

    assigned = [False] * len(valid_candidates)
    mandatory = []

    for i in range(len(required_bits)):
        found = False
        for idx in covered_by[i]:
            if not assigned[idx]:
                assigned[idx] = True
                mandatory.append(idx)
                found = True
                break
        if not found:
            # すでに誰かが担当している場合でもOK（被りあり）
            # 最低1人は必要なので、被ってもよい
            # ただし、全員が既にassignedなら新しい人がいない
            # ここでは、各bitに1人以上割り当てられていればOK
            pass

    # 実際には、各bitをカバーする人がいれば良いので、貪欲に各bitに1人割り当て
    # 被らないようにするのが最適とは限らないので、別の方法を考える

    # 効率的な方法:
    # 1. valid_candidatesの中で、Kの禁止ビットを持たないもののみを使う
    # 2. その中で、ORをK以下に保ちながら最大の部分集合を選ぶ
    # 3. さらに、ORがちょうどKになるようにする

    # これは部分集合のORがKになるものを選ぶ問題
    # 半分全列挙はN=2*10^5では無理

    # 別のアイデア：
    # 候補者をフィルタリングした後、ORがKを超えない最大部分集合を取り、それがKに一致するか見る
    # しかし、最大部分集合のORがK未満でも、他の候補者を追加することでKにできるかもしれない

    # 高速化のため、Kのビットが立っている箇所に注目
    # 各候補者のうち、Kで0のビットに1を持たないもののみ有効

    # Kで0のビットに1を持つ候補者は除外
    # 残った候補者のORがKと一致する最大部分集合を探す

    # 最大独立集合のような問題だが、今回はORがKと一致する最大部分集合

    # 重要な観察：ORがKと一致する ⇔ 
    # 1. すべての候補者のOR <= K （Kで0のビットに1がない）
    # 2. すべてのKで1のビットについて、少なくとも1人が持っている

    # ステップ:
    # 1. 無効な候補者を除外（Kで0のビットに1を持つ）
    # 2. 残った候補者のうち、Kの各ビットをカバーする人がいるかチェック
    # 3. カバーされているなら、最大人数を選ぶ

    # 最大人数の選び方：
    # 各required bitについて最低1人は必要 → 最低人数はその数
    # 残りは好きに選んでよい（ただしORがKを超えないように）

    # 実装:
    # まず、各候補者がKの禁止ビットを持つか判定
    # 次に、Kの各ビットが誰かにカバーされているか判定
    # 最後に、最大の部分集合を構築

    # 判定後、最大人数を求める
    # 貪欲に、各ビットをカバーする最小人数を選び、残りは全部選ぶ

    # 各required bitをカバーする最小の候補者を選ぶ
    # これはset cover problemでNP-hardだが、貪欲近似で良い
    # ただし、今回は各ビットをカバーする人がいれば良いので、各ビットに1人割り当てればOK

    # つまり、各required bitに対して1人ずつ選び、残りは全部選んでもOK

    # 実装:
    # covered_by[i]: required_bits[i]をカバーする候補者のindexリスト
    # 各ビットをカバーする人がいればOK
    # 各ビットから1人ずつ選ぶ（できるだけ重複を避けて）
    # 残りは全部選んでもORはKを超えない

    # 最小カバーを求める: 各ビットから1人ずつ選ぶ
    # これは最小ヒープなどで貪欲に選んでも良いが、今回は単純に各ビットから1人選ぶだけで良い
    # 重複を許すと人数が減るので、重複を避けるのが良い

    # ただし、ビット数は最大60程度なので、各ビットから1人ずつ選ぶのは現実的

    # 実装:
    from collections import defaultdict
    import heapq

    # 各候補者がカバーするrequired bitsのリスト
    candidate_covers = []
    for i, a in enumerate(valid_candidates):
        covers = []
        for j, bit_pos in enumerate(required_bits):
            if a & (1 << bit_pos):
                covers.append(j)
        candidate_covers.append((len(covers), i, covers))  # (被覆数, index, 被覆リスト)

    # 被覆数が多い順にソートして、貪欲に選ぶ
    candidate_covers.sort(reverse=True)

    # 各ビットがカバーされているか
    covered = [False] * len(required_bits)
    selected_indices = set()

    # 各ビットをカバーするために候補者を選択
    for _, idx, covers in candidate_covers:
        added = False
        for bit_idx in covers:
            if not covered[bit_idx]:
                added = True
        if added:
            selected_indices.add(idx)
            for bit_idx in covers:
                covered[bit_idx] = True

    # すべてのビットがカバーされたか確認
    if not all(covered):
        print(-1)
        return

    # 残りの候補者はすべて選んでもOK（ORがKを超えない）
    total_selected = len(valid_candidates)
    print(total_selected)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.