← 返回题目列表

AtCoder · awc0100_c

C. 权限管理系统

中文机器翻译题面 查看原题

分数: 266 分

问题陈述

Takahashi 是一家公司的系统管理员。公司拥有 N 类型的资源,每个资源都有一组访问它所需的权限。权限包括 L 权限项,以及需要的权限 i-th 资源由位串表示 S_i 长度 L。位串是由以下组成的串 0 和 1,其中最左边的位是最高有效位 (MSB)。当 p第位(1 \leq p \leq L,将最左边的位算为第 1 位)的位串为 访问该资源需要 1,这意味着 p-th 权限项。

授予员工的访问权限也由位串表示 K 长度 L。员工访问资源的条件 i 是员工拥有该资源所需的所有权限项。换句话说,对于每个位位置,如果 S_i is 1,则位于相同位置的位 K 还必须是 1 (即按位 AND 满足 K \mathbin{\&} S_i = S_i).

Aoki 是公司的安全官,提倡不授予不必要的广泛权限的政策。青木给了高桥 Q 请求。在 j第一个请求 (1 \leq j \leq Q),数量 指定某个员工需要访问的 M_j 资源: c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} (同一请求中资源编号可能重复)。所有权限位串中 K 允许访问所有指定的资源,找到当位串被解释为二进制数时其值最小的一个。

请注意,允许访问所有指定资源的权限位串始终存在(例如,所有位都设置为 1 满足条件)。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq L \leq 64
  • 1 \leq Q \leq 10^5
  • S_i 是一个长度为 L 组成 0 和 1 (1 \leq i \leq N)
  • M_j 是指定的资源数量 j第一个请求,以及 1 \leq M_j \leq N (1 \leq j \leq Q)
  • c_{j,k} 是在 j第一个请求,以及 1 \leq c_{j,k} \leq N (1 \leq j \leq Q, 1 \leq k \leq M_j)
  • 同一请求中的资源编号可能重复
  • \sum_{j=1}^{Q} M_j \leq 10^5
  • S_i 作为字符串给出;所有其他输入均为整数

输入

N L Q
S_1
S_2
\vdots
S_N
M_1 c_{1,1} c_{1,2} \ldots c_{1,M_1}
M_2 c_{2,1} c_{2,2} \ldots c_{2,M_2}
\vdots
M_Q c_{Q,1} c_{Q,2} \ldots c_{Q,M_Q}
  • 第一行包含三个空格分隔的整数: N 代表资源类型的数量, L 表示位串的长度,以及 Q 代表请求数。
  • 第 2 行至 N+1 为每个资源提供所需的权限。
  • 线 1 + i (1 \leq i \leq N) 提供所需的权限 S_i 为 i-th 资源作为长度的字符串 L 组成 0 和 1。最左边的字符是最高有效位。
  • 以下 Q 行给出每个请求。
  • 线 N + 1 + j (1 \leq j \leq Q) 给出 j-第一个请求:第一个整数 M_j 表示要访问的资源数量,后跟空格分隔的整数 c_{j,1}, c_{j,2}, \ldots, c_{j,M_j} 代表要访问的资源编号。资源编号是介于 1 和 N 包括在内。同一请求中的资源编号可能会重复。

输出

输出 Q 行。上 j- 第行 (1 \leq j \leq Q),输出允许访问指定的所有资源的权限位串 j第一个请求,当解释为二进制数时具有最小值。将其输出为长度的字符串 L 组成 0 和 1 ,最左边的位是最高有效位(如果长度小于 L,带前导的垫 0s 确保字符串的长度准确 L).


示例输入 1

3 4 3
1010
0110
1001
1 1
2 1 2
3 1 2 3

示例输出 1

1010
1110
1111

示例输入 2

5 8 4
10100000
01010000
00001010
00000101
11000011
1 3
2 1 3
3 2 4 5
4 1 2 3 4

示例输出 2

00001010
10101010
11010111
11111111

示例输入 3

6 16 5
1000000000000001
0100000000000010
0010000000000100
0001000000001000
0000100000010000
1111100000000000
2 1 2
3 1 3 5
1 6
4 2 3 4 5
6 1 2 3 4 5 6

示例输出 3

1100000000000011
1010100000010101
1111100000000000
0111100000011110
1111100000011111