#CW46. 复原排列(permutation)
复原排列(permutation)
题目描述
小 W 有一个 到 的排列 。对于每个位置 ,定义
小 Z 看到每个位置的一条信息:p x 表示 ,s x 表示 。这些信息由同一个排列产生,因此至少存在一个满足全部信息的排列。请输出任意一个满足条件的排列。
输入格式
第一行是整数 ,表示测试用例数。
每个测试用例的第一行是整数 。接下来 行按 的顺序给出信息。每行包含一个字符 p 或 s,以及一个整数 :
p x:要求 ;s x:要求前缀逆序对数 。
输出格式
对每个测试用例输出一行 个整数,表示一个排列 。输出的排列必须同时满足输入中的所有信息。
本题答案不唯一,评测使用特殊校验:只要输出是合法的 排列且满足全部信息即视为正确。
样例 1 输入
2
3
s 0
p 2
s 3
4
p 4
s 1
p 2
s 3
样例 1 输出
3 2 1
4 1 2 3
第二组数据中,前缀 有一个逆序对,前缀 有三个逆序对。
数据范围与子任务
保证 ,,且所有测试用例的 之和不超过 。所有 p 信息中的 属于 ,所有 s 信息中的 属于 ,并且信息一定来自至少一个排列。
| 子任务 | 分值 | 测试点 | 额外限制 |
|---|---|---|---|
| 1 | 10 | , | |
| 2 | 20 | , | |
| 3 | 每条信息均为 s 类型 | ||
| 4 | 50 | 无额外限制 |