Overview

For each query, find the minimum permission bit string that grants access to all specified resources.

Discussion

Each resource has a required permission given as a bit string. An employee can access that resource if and only if the employee’s permission bit string \(K\) “contains” the resource’s required bit string \(S_i\), i.e., \(K \mathbin{\&} S_i = S_i\).

To access all of multiple resources, the employee must possess all permissions required by each resource. In other words, they need to have the union of all required permissions.

This corresponds to the OR operation in bitwise arithmetic. That is, by taking the OR of the required permission bit strings of all relevant resources, we obtain the minimum permissions the employee must have.

For example, if resource 1 requires 1100 and resource 2 requires 1010, then to access both, 1100 | 1010 = 1110 is needed.

The bit string obtained this way is trivially the smallest when viewed as a binary number (it is impossible to achieve the same coverage with fewer bits set), so this is the answer.

Naively checking all bits for each query to aggregate permissions would be inefficient, but using bitwise operations allows us to process this quickly.

Algorithm

1. Pre-convert each resource’s required permission bit string \(S_i\) into an integer (bit string) and store it.
2. For each query:
   • Retrieve all \(S_i\) corresponding to the resources to be accessed,
   • Take the OR of all those bit strings to obtain the minimum required permissions.
3. Convert the resulting integer back into a bit string (character string) and output it.

Complexity

• Time complexity: \(O(NL + Q(M + L))\)
  • Pre-processing to convert \(N\) bit strings to integers: \(O(NL)\)
  • For each query, taking the OR of up to \(M\) bit strings: \(O(M)\)
  • Converting the result back to a bit string: \(O(L)\)
• Space complexity: \(O(N + L)\)
  • An array to store the bit strings as integers, and a temporary bit list for output

Implementation Notes

• Since the leftmost position of the bit string is the most significant bit (MSB), care must be taken with bit positions when shifting.

• Resource numbers are given as 1-indexed in the input, so they need to be converted to 0-indexed internally.

• sys.stdin.read is used for fast input reading.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    # リソースの必要権限を整数に変換
    S = []
    for _ in range(N):
        s = data[idx]; idx += 1
        num = 0
        for i in range(L):
            if s[i] == '1':
                num |= (1 << (L - 1 - i))
        S.append(num)
    
    results = []
    for _ in range(Q):
        M = int(data[idx]); idx += 1
        resources = list(map(int, data[idx:idx+M])); idx += M
        # リソース番号を0-indexedに変換
        required = [S[r - 1] for r in resources]
        # すべての必要な権限のORを取る
        permission = 0
        for req in required:
            permission |= req
        # permissionをビット列に戻す
        bits = []
        for i in range(L):
            if permission & (1 << (L - 1 - i)):
                bits.append('1')
            else:
                bits.append('0')
        results.append(''.join(bits))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

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