AT_abc282_f [ABC282F] Union of Two Sets

题目描述

本题为交互式问题（你的程序将与评测程序通过标准输入输出进行交互）。

你和评测程序将按照如下步骤进行操作。操作分为第 $1$ 阶段和第 $2$ 阶段，首先进行第 $1$ 阶段，紧接着进行第 $2$ 阶段。

（第 $1$ 阶段）

• 评测程序会给出一个整数 $N$。
• 你需要输出一个 $1$ 到 $50000$ 之间的整数 $M$。
• 此外，你还需要输出 $M$ 个整数对 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$，其中对于所有 $i = 1, 2, \ldots, M$，都有 $1 \leq l_i \leq r_i \leq N$。这些整数对可以重复。

（第 $2$ 阶段）

• 评测程序会给出一个整数 $Q$。
• 接下来，你和评测程序将重复以下操作 $Q$ 次：
  • 评测程序会给出两个整数 $L, R$ 作为一次查询。
  • 你需要输出两个 $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$ 阶段）

• 首先，输入给出 $N$。
• 然后，你需要输出一个 $1$ 到 $50000$ 之间的整数 $M$。
• 接下来，你需要输出 $M$ 行，每行输出一对整数 $l_i\ r_i$，表示 $(l_i, r_i)$。

（第 $2$ 阶段）

• 首先，输入给出 $Q$。

• 每次查询，输入会给出两个整数 $L\ R$。

• 对于每次查询，你需要输出两个整数 $a\ b$。

输出格式

（第 $1$ 阶段）

• 输出一个整数 $M$。
• 接下来输出 $M$ 行，每行两个整数 $l_i\ r_i$。

（第 $2$ 阶段）

• 对于每次查询，输出一行两个整数 $a\ b$。

说明/提示

约束条件

• $1 \leq N \leq 4000$
• $1 \leq Q \leq 10^5$
• $1 \leq L \leq R \leq N$
• 所有输入均为整数。

注意事项

• 每次输出后请务必输出换行并刷新标准输出，否则可能会因超时（TLE）被判为错误。
• 如果在交互过程中输出不合法，或程序中途退出，评测结果不确定。 特别是，如果程序运行时发生运行时错误，评测结果可能不是 RE，而是 WA 或 TLE。
• 第 $2$ 阶段结束后请立即终止程序，否则评测结果不确定。
• 第 $2$ 阶段中给出的 $L, R$ 会根据你在第 $1$ 阶段输出的 $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ 决定。

输入输出样例

以下为 $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 第 $1$ 次查询，$L = 1, R = 3$。
1 5 你输出 $a = 1, b = 5$。
3 4 第 $2$ 次查询，$L = 3, R = 4$。
2 1 你输出 $a = 2, b = 1$。
2 4 第 $3$ 次查询，$L = 2, R = 4$。
4 4 你输出 $a = 4, b = 4$。
1 1 第 $4$ 次查询，$L = 1, R = 1$。
3 3 你输出 $a = 3, b = 3$。

由 ChatGPT 4.1 翻译