QOJ.ac

QOJ

Time Limit: 20 s Memory Limit: 2048 MB Total points: 14

#12495. 彩虹排序

Statistics

你的朋友 Charles 给你出了一个挑战。他在桌子上放了 $N$ 张牌,并按他选择的顺序排成一行。每张牌都有一个颜色,且每种颜色可以出现在一张或多张牌上。

Charles 要求你在不改变他所选顺序的情况下,在每张牌上写下一个正整数,使得:

  1. 当从左到右读取牌时,你写下的整数呈非递减顺序。
  2. 相同颜色的牌上写有相同的整数。
  3. 不同颜色的牌上写有不同的整数。

最后,Charles 希望你按照所写整数的升序对颜色进行排序。例如,如果蓝色牌上的数字是 $2$,红色牌上的数字是 $5$,绿色牌上的数字是 $3$,那么颜色的顺序将是蓝色、绿色、红色。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含整数 $N$。下一行包含 $N$ 个整数 $S_1, S_2, \dots, S_N$,其中 $S_i$ 表示从左往右第 $i$ 张牌的颜色。

输出格式

对于每个测试用例,输出一行 Case #x: y,其中 $x$ 是测试用例编号(从 $1$ 开始),$y$ 是按要求顺序排列的颜色集合(每种颜色仅列出一次)。如果无法在满足所有规则的情况下为给定的牌写下整数,则 $y$ 必须为 IMPOSSIBLE

数据范围

$1 \le T \le 100$。 $1 \le S_i \le 10^5$,对于所有 $i$。

子任务 1

$1 \le N \le 10$。

子任务 2

$1 \le N \le 10^5$。

样例

样例输入 1

2
4
3 8 8 2
5
3 8 2 2 8

样例输出 1

Case #1: 3 8 2
Case #2: IMPOSSIBLE

说明

在样例 #1 中,有 $3$ 种不同的颜色分布在 $4$ 张牌上。一种可能的解法是按顺序写下以下整数:$1, 2, 2, 3$。注意,颜色 $8$ 的两张牌上都写了相同的整数 ($2$)。此时,颜色的顺序为 $3, 8, 2$。

在样例 #2 中,令 $c_8$ 和 $c_2$ 分别为颜色 $8$ 和 $2$ 的牌上所写的整数。如果 $c_2 > c_8$,则最右侧的两张牌上的整数将不是非递减的。如果 $c_2 < c_8$,则从左往右数第二张和第三张牌将不满足非递减。最后,$c_8 = c_2$ 被规则禁止。因此,本例中不存在有效的整数填写方式。

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.