← 返回题目列表

Codeforces · 1413/D

D. 手里剑

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

Tenten 经营一家忍者武器店。今天,她愿意出售 $$$n$$$ 手里剑,价格为 $$$1$$$、$$$2$$$、...、$$$n$$$ ryo(当地货币)。在一天中,Tenten 会将手里剑放在陈列柜上,而陈列柜在一天开始时是空的。她的工作相当简单:有时 Tenten 会在陈列柜上放置另一把手里剑(来自可用的手里剑),有时忍者会进来并从陈列柜中购买一把手里剑。由于忍者很节俭,他们总是从陈列柜里购买最便宜的手里剑。

Tenten 保留了所有事件的记录,她最终得到了以下类型记录的列表:

- + 表示她在陈列柜上放置了另一把手里剑;
- - x表示购买了价格$$$x$$$的手里剑。

今天是个幸运日,手里剑都买完了。现在,腾腾想知道她的清单是否一致,以及将手里剑放在展示柜上的可能顺序是什么。帮她找出这个!

输入

第一行包含唯一的整数 $$$n$$$ ($$$1\leq n\leq 10^5$$$) 代表手里剑的数量。

以下 $$$2n$$$ 行以上述格式描述事件。保证第一种类型的事件恰好有 $$$n$$$ 个,并且从 $$$1$$$ 到 $$$n$$$ 的每个价格在第二种类型的事件中恰好出现一次。

输出

如果列表一致,则打印“YES”。否则(即,如果列表是矛盾的并且没有有效的手里剑放置顺序),则打印“NO”。

在第一种情况下,第二行必须包含 $$$n$$$ 以空格分隔的整数,表示手里剑的价格(按放置顺序排列)。如果有多个答案,请打印其中一个。

示例

输入 #1

4
+
+
- 2
+
- 3
+
- 1
- 4

输出 #1

YES
4 2 3 1

输入 #2

1
- 1
+

输出 #2

NO

输入 #3

3
+
+
+
- 2
- 1
- 3

输出 #3

NO

注意

在第一个示例中,Tenten 首先放置了价格为 $$$4$$$ 和 $$$2$$$ 的手里剑。此后,一位顾客进来买了最便宜的手里剑,价格为$$$2$$$。接下来,Tenten 在已经放置的 $$$4$$$-ryo 中添加了展示柜上价格为 $$$3$$$ 的手里剑。然后一位新顾客买了这个$$$3$$$-ryo shuriken。之后她添加了一把$$$1$$$-ryo手里剑。最后两位顾客分别购买了手里剑$$$1$$$和$$$4$$$。请注意,顺序 $$$[2, 4, 3, 1]$$$ 也是有效的。

在第二个示例中,第一位顾客在放置任何东西之前就购买了手里剑,这显然是不可能的。

在第三个示例中,Tenten 将她所有的手里剑都放在了展示柜上,之后一位顾客进来并以 $$$2$$$ 的价格购买了手里剑。这是不可能的,因为手里剑不是最便宜的,我们知道 $$$1$$$-ryo 手里剑也在那里。