A13821. Lookup Tables
编程题
普及/提高-
知识点
题目描述
The first line contains two integers $K$ and $Q$ ( $ 1 <= K <= 16$ , $1 <= Q <= 2\cdot 10^5$ ).
Each of the next $Q$ lines contains three integers $l_i$ , $r_i$ and $v_i$ . ( $0 \leq l_i \leq r_i < 2^{2K}$ , $0 \leq v_i < 2^{16}$ ).
Each of the next $Q$ lines contains three integers $l_i$ , $r_i$ and $v_i$ . ( $0 \leq l_i \leq r_i < 2^{2K}$ , $0 \leq v_i < 2^{16}$ ).
输入格式
On the first line output "possible" (without quotes) if two tables satisfying the conditions exist, or "impossible" (without quotes) if they don't exist.
If a solution exists, in the next $2 \cdot 2^K$ lines your program should output all values of the two lookup tables (LSBTable and MSBTable) it found. When there are multiple pairs of tables satisfying the conditions, your program may output any such pair.
On lines $1 + i$ output $\textrm{LSBTable}[i]$ . ( $0 \leq i < 2^K$ , $0 \leq \textrm{LSBTable}[i] < 2^{16}$ ).
On lines $1 + 2^K + i$ output $\textrm{MSBTable}[i]$ . ( $0 \leq i < 2^K$ , $0 \leq \textrm{MSBTable}[i] < 2^{16}$ ).
If a solution exists, in the next $2 \cdot 2^K$ lines your program should output all values of the two lookup tables (LSBTable and MSBTable) it found. When there are multiple pairs of tables satisfying the conditions, your program may output any such pair.
On lines $1 + i$ output $\textrm{LSBTable}[i]$ . ( $0 \leq i < 2^K$ , $0 \leq \textrm{LSBTable}[i] < 2^{16}$ ).
On lines $1 + 2^K + i$ output $\textrm{MSBTable}[i]$ . ( $0 \leq i < 2^K$ , $0 \leq \textrm{MSBTable}[i] < 2^{16}$ ).
输出格式
A closed interval $[a, b]$ includes both a and b.
In the first sample, tables $\textrm{LSBTable} = [1,3]$ and $\textrm{MSBTable} = [1,3]$ satisfy the conditions: $F[0] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[0] = 1 \& 1 = 1$ , $F[1] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[0] = 3 \& 1 = 1$ , $F[2] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[1] = 1 \& 3 = 1$ , $F[3] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[1] = 3 \& 3 = 3$ .
In the second sample, tables $\textrm{LSBTable} = [3,3,2,2]$ and $\textrm{MSBTable} = [0,3,0,1]$ satisfy all the conditions.
In the third sample there are no two lookup tables which can satisfy the conditions.
In the first sample, tables $\textrm{LSBTable} = [1,3]$ and $\textrm{MSBTable} = [1,3]$ satisfy the conditions: $F[0] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[0] = 1 \& 1 = 1$ , $F[1] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[0] = 3 \& 1 = 1$ , $F[2] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[1] = 1 \& 3 = 1$ , $F[3] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[1] = 3 \& 3 = 3$ .
In the second sample, tables $\textrm{LSBTable} = [3,3,2,2]$ and $\textrm{MSBTable} = [0,3,0,1]$ satisfy all the conditions.
In the third sample there are no two lookup tables which can satisfy the conditions.
输入输出样例
输入 #1
1 2 0 2 1 3 3 3
输出 #1
possible 1 3 1 3
输入 #2
2 4 4 5 3 6 7 2 0 3 0 12 13 1
输出 #2
possible 3 3 2 2 0 3 0 1
输入 #3
2 3 4 4 3 5 6 2 12 14 1
输出 #3
impossible
说明/提示
A closed interval $[a, b]$ includes both a and b.
In the first sample, tables $\textrm{LSBTable} = [1,3]$ and $\textrm{MSBTable} = [1,3]$ satisfy the conditions: $F[0] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[0] = 1 \& 1 = 1$ , $F[1] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[0] = 3 \& 1 = 1$ , $F[2] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[1] = 1 \& 3 = 1$ , $F[3] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[1] = 3 \& 3 = 3$ .
In the second sample, tables $\textrm{LSBTable} = [3,3,2,2]$ and $\textrm{MSBTable} = [0,3,0,1]$ satisfy all the conditions.
In the third sample there are no two lookup tables which can satisfy the conditions.
In the first sample, tables $\textrm{LSBTable} = [1,3]$ and $\textrm{MSBTable} = [1,3]$ satisfy the conditions: $F[0] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[0] = 1 \& 1 = 1$ , $F[1] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[0] = 3 \& 1 = 1$ , $F[2] = \textrm{LSBTable}[0] \& \textrm{MSBTable}[1] = 1 \& 3 = 1$ , $F[3] = \textrm{LSBTable}[1] \& \textrm{MSBTable}[1] = 3 \& 3 = 3$ .
In the second sample, tables $\textrm{LSBTable} = [3,3,2,2]$ and $\textrm{MSBTable} = [0,3,0,1]$ satisfy all the conditions.
In the third sample there are no two lookup tables which can satisfy the conditions.