QOJ.ac

QOJ

Limite de temps : 5 s Limite de mémoire : 1024 MB Points totaux : 100

#12146. 拼图礼物

Statistiques

Julia 正在为 James 准备一份礼物。她将从她拥有的 $n$ 个拼图中挑选一些送给他,其中第 $i$ 个拼图($1 \le i \le n$)包含 $x_i$ 个碎片,难度为 $y_i$(如果拼图非常简单,难度可以是负数)。

James 非常兴奋,他想提前知道自己会收到什么。因此,他利用自己的一些“犯罪能量”获取了关于这份礼物的信息。具体来说,他设法获得了一条加密信息,其中包含了所有他将收到的拼图的碎片总数和难度总和。

现在他想知道,是否值得花更多时间去解密这条信息。毕竟,这些信息可能不足以唯一确定他的礼物。由于他不擅长这些计算机玩意儿,James 向你寻求帮助。请帮他找出是否值得解密这条信息。如果答案是否定的,你必须找出两个导致相同加密信息的不同礼物。

输入格式

输入包含: 一行一个整数 $n$($2 \le n \le 4\,096$),表示 Julia 拥有的拼图数量。 $n$ 行,第 $i$ 行包含两个整数 $x_i$ 和 $y_i$($1 \le x_i \le 4\,096$,$|y_i| \le 4\,096$),分别表示第 $i$ 个拼图的碎片数量和难度。

输出格式

如果 James 可以唯一确定他的礼物,则打印 “yes”。否则,打印 “no”,并紧接着输出两行,每行包含一份礼物的描述。礼物的描述应以一个整数 $k$ 开头,表示拼图的数量,随后是 $k$ 个不同的整数,即拼图的索引。

注意,这两份礼物必须是不同的,这意味着至少有一个拼图存在于其中一份礼物中,但不在另一份礼物中。

如果存在多组导致相同加密信息的礼物,你可以打印其中任意一组。

样例

输入格式 1

5
2 -1
3 2
3 1
1 -3
1 1

输出格式 1

no
3 2 4 5
2 1 3

说明

在第一个样例中,第一份礼物由拼图 2、4 和 5 组成。碎片总数为 $3+1+1 = 5$,难度总和为 $2+(-3)+1 = 0$。第二份礼物由拼图 1 和 3 组成。碎片总数为 $2+3 = 5$,难度总和为 $(-1)+1 = 0$。因此,如果 James 只知道碎片总数和难度总和,他无法恢复他的礼物。所以不值得解密这条信息。

输入格式 2

4
2 -1
3 2
3 1
1 -3

输出格式 2

yes

说明

在第二个样例中,无论 Julia 准备什么礼物,如果 James 知道碎片总数和难度总和,他都能恢复他的礼物。所以他应该解密这条信息。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.