102825: [AtCoder]ABC282 F - Union of Two Sets
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $500$ points
Problem Statement
This is an interactive task, where your and the judge's programs interact via Standard Input and Output.
You and the judge will follow the procedure below. The procedure consists of phases $1$ and $2$; phase $1$ is immediately followed by phase $2$.
(Phase $1$)
- The judge gives you an integer $N$.
- You print an integer $M$ between $1$ and $50000$, inclusive.
- You also print $M$ pairs of integers $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ such that $1 \leq l_i \leq r_i \leq N$ for every $i = 1, 2, \ldots, M$ (the $M$ pairs do not have to be distinct).
(Phase $2$)
- The judge gives you an integer $Q$.
-
You and the judge repeats the following $Q$ times.
- The judge gives you two integers $L$ and $R$ as a query.
-
You respond with two integers $a$ and $b$ between $1$ and $M$, inclusive (possibly with $a = b$).
Here, $a$ and $b$ must satisfy the condition below. Otherwise, your submission will be judged incorrect.
- The union of the set $\lbrace l_a, l_a+1, \ldots, r_a\rbrace$ and the set $\lbrace l_b, l_b+1, \ldots, r_b\rbrace$ equals the set $\lbrace L, L+1, \ldots, R\rbrace$.
After the procedure above, terminate the program immediately to be judged correct.
Constraints
- $1 \leq N \leq 4000$
- $1 \leq Q \leq 10^5$
- $1 \leq L \leq R \leq N$
- All values in the input are integers.
Input and Output
This is an interactive task, where your and the judge's programs interact via Standard Input and Output.
(Phase $1$)
- First, $N$ is given from the input.
- Next, an integer $M$ between $1$ and $50000$, inclusive, should be printed.
- Then, $(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$ should be printed, one at a time. Specifically, for each $i = 1, 2, \ldots, M$, the $i$-th output should be $(l_i, r_i)$ in the following format:
$l_i$ $r_i$
(Phase $2$)
- First, $Q$ is given from the input.
- In each query, integers $L$ and $R$ representing the query are given in the following format:
$L$ $R$
- In response to each query, two integers $a$ and $b$ should be printed in the following format:
$a$ $b$
Cautions
- At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE
Input
题意翻译
**这是一道交互题** - 首先，给出一个正整数 $n$ （$1\le n\le 4000$），你需要构造 $m$（$1\le m\le 50000$） 个区间 $[l_i,r_i]$，满足 $1\le l_i \le r_i \le n$，输出 $m$ 和这 $m$ 个区间，这些区间的编号按输出顺序依次为 $1,2,\cdots ,m$。 - 然后，给出一个正整数 $q$（$1\le q\le 10^5$），表示有 $q$ 次询问。对于每次询问，给定区间 $[l,r]$，你要找到两个整数 $i,j$（$1\le i,j \le m$，$i$ 可以等于 $j$），满足在第一步中构造的区间中 $[l_i,r_i]$ 与 $[l_j,r_j]$ 的并集等于 $[l,r]$，输出 $[i,j]$。Output
分数：500分
问题描述
这是一个交互式任务，你和裁判的程序通过标准输入和输出进行交互。
你和裁判将遵循以下过程。过程包括阶段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$（这$M$对整数不必不同）。
(阶段2)
- 裁判给你一个整数$Q$。
- 你和裁判重复以下$Q$次。
- 裁判给你两个整数$L$和$R$作为查询。
- 你回答两个介于1和$M$之间的整数$a$和$b$（可能有$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$。
- 接下来，应该打印一个介于1和50000之间的整数$M$。
- 然后，$(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M)$应该一次打印出来。具体来说，对于每一个$i = 1, 2, \ldots, M$，第$i$个输出应该以以下格式打印$(l_i, r_i)$：
$l_i$ $r_i$
(阶段2)
- 首先，从输入中给出$Q$。
- 对于每次查询，表示查询的整数$L$和$R$将以以下格式给出：
$L$ $R$
- 对