← 返回题目列表

AtCoder · abc282_f

I. 两组的并集

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

分数: 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.