分数: 500 点
问题陈述
这是一个 交互式任务,您和法官的程序通过标准输入和输出进行交互。
您和法官将遵循以下程序。 该过程由几个阶段组成 1 和 2;阶段 1 紧接着是阶段 2.
(相 1)
- 法官给你一个整数 N.
- 你打印一个整数 M 之间 1 和 50000,包括在内。
- 您还打印 M 整数对 (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) 这样 1 \leq l_i \leq r_i \leq N 对于每个 i = 1, 2, \ldots, M ( M 对不必不同)。
(相 2)
- 法官给你一个整数 Q.
- 您和法官重复以下内容 Q 次。
- 法官给你两个整数 L 和 R 作为查询。
- 您用两个整数进行响应 a 和 b 之间 1 和 M,包含在内(可能与 a = b)。
在这里, a 和 b 必须满足以下条件。否则,您的提交将被判定为不正确。
- 集合的并集 \lbrace l_a, l_a+1, \ldots, r_a\rbrace 和设置 \lbrace l_b, l_b+1, \ldots, r_b\rbrace 等于集合 \lbrace L, L+1, \ldots, R\rbrace.
完成上述过程后,立即终止程序即可判断正确。
约束
- 1 \leq N \leq 4000
- 1 \leq Q \leq 10^5
- 1 \leq L \leq R \leq N
- 输入中的所有值都是整数。
输入和输出
这是一项交互式任务,您和法官的程序通过标准输入和输出进行交互。
(相 1)
- 首先, N 由输入给出。
- 接下来,一个整数 应打印 M 之间 1 和 50000(含)。 应一次打印一个
- 然后, (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) 。 具体来说,对于每个 i = 1, 2, \ldots, M, i-th 输出应该是 (l_i, r_i) 采用以下格式:
l_i r_i
(相 2)
- 首先, Q 由输入给出。
- 在每个查询中,整数 表示查询的 L 和 R 按以下格式给出:
L R
- 响应每个查询,两个整数 a 和 b 应按以下格式打印:
a b
注意事项
- 在每个输出的末尾,打印换行符并刷新标准输出。否则,您可能会得到 TLE 判决。
- 如果您的程序打印格式错误的输出或过早退出,则结论将是不确定的。 特别注意,如果出现运行时错误,判决可能是 or TLE 而不是 .
- 阶段后 2,立即终止程序。否则,判决将是不确定的。
- L 和 R 相位给定 2 将根据 (l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) 你按阶段打印 1.
示例交互
下面是与 N = 4 和 Q = 4.
| 输入 | 输出 | 说明 给出了 |
|---|---|---|
4 |
N 。 | |
6 |
您打印 M. | |
3 3 |
您打印 (l_1, r_1) = (3, 3). | |
4 4 |
您打印 (l_2, r_2) = (4, 4). | |
1 1 |
您打印 (l_3, r_3) = (1, 1). | |
2 4 |
您打印 (l_4, r_4) = (2, 4). | |
1 3 |
您打印 (l_5, r_5) = (1, 3). | |
2 2 |
您打印 (l_6, r_6) = (2, 2). | |
4 |
Q 。 | |
1 3 |
作为第一个查询, 给出了 L = 1 和 R = 3 。 | |
1 5 |
您回复 a = 1 和 b = 5. | |
3 4 |
作为第二个查询, L = 3 和 R = 4 。 | |
2 1 |
您回复 a = 2 和 b = 1. | |
2 4 |
作为第三个查询, L = 2 和 R = 4 。 | |
4 4 |
您回复 a = 4 和 b = 4. | |
1 1 |
作为第四个查询, L = 1 和 R = 1 。 | |
3 3 |
您回复 a = 3 和 b = 3. | |