← 返回题目列表

Codeforces · 788/D

D. 查找线

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

经过一些编程比赛后,罗马决定尝试旅游业。他的祖国乌兹利亚是一个笛卡尔平面。他想沿着乌日扬迪亚的每条主要直线行走。已知这些线中的每一条都是平行于其中一个轴的直线(即用方程 x = a 或 y = a 来描述,其中 a 是称为该线的坐标的整数)。

罗马丢失了自己的地图,所以他首先应该找出所有线路的坐标。安东叔叔同意帮助他,遵循以下规则:

- 最初 Roma 不知道垂直线和水平线的数量及其坐标;
- 罗马可以公布乌日兰迪亚某个点的整数坐标,然后安东会告诉他从所选点到每条线的距离的最小值。然而,由于线的坐标绝对值不超过108,因此罗马无法选择坐标绝对值超过108的点。

安东叔叔正赶着去UOI(乌日兰信息学奥林匹克竞赛),所以他只能回答不超过3·105个问题。

问题是 Roma 不知道如何找出线的坐标。编写一个程序来扮演 Roma 的角色并找到坐标。

输入

最初没有输入。您的程序应该进行查询来获取信息。

保证每种类型的水平线和垂直线数量至少为 1 条且小于或等于 104 条。

互动

要进行查询,请打印一行“0 x y”(-108 ≤ x,y ≤ 108),其中 x 和 y 是点的坐标。在每个查询之后,您需要打印行尾,进行“刷新”操作,然后读取查询的答案 - 从该点到乌日良迪亚主直线的距离中的最小值。

您最多可以进行 3·105 条查询。

当您准备好打印答案时,请打印三行:

1. 在第一行中打印“1 nm”,其中 n 是垂直线数(平行于 OY),m 是水平线数(平行于 OX)。
2. 在第二行中打印 n 个整数 x1, x2, ..., xn ——垂直线的坐标。
3. 在第三行以相同的格式打印 m 个整数 y1, y2, ..., ym ——水平线的坐标。

您可以按任意顺序打印坐标。

要进行“刷新”,您可以使用(在打印查询/答案和行尾之后):

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

如果您提出的查询超出允许的数量或提出无效查询,您将得到错误答案。

如果您不打印任何内容或忘记刷新输出,则可能会出现空闲限制超出。

如果您的程序在任何时候读取 -1 作为答案,它应该立即正常退出(例如,通过调用 exit(0))。在这种情况下,您将得到错误答案,这意味着您进行的查询超出了允许的范围,或者进行了无效查询。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。

进行黑客测试

第一行应包含两个整数 n 和 m (1 ≤ n, m ≤ 104)。

第二行应包含 n 个不同的整数 xi (-108 ≤ xi ≤ 108) — 垂直线的坐标。

第三行应包含 m 个不同的整数 yi (-108 ≤ yi ≤ 108) — 水平线的坐标。

您可以按任意顺序写入坐标。

您可以在注释中查看示例案例。

示例

输入 #1

1
1
3
2

输出 #1

0 1 2
0 -2 -2
0 5 6
0 -2 2
1 1 2
2
0 -3

注意

示例测试是

最小距离为:

- 从 (1, 2) 到 x = 2;
- 从 ( - 2,  - 2) 到 y =  - 3;
- 从 (5, 6) 到 x = 2;
- 从 ( - 2, 2) 到 y = 0。