题目背景
通过远古档案馆的探索,你成功制出了天体探测仪,你需要用它发现潜藏的天体科技。
题目描述
想要找到天体科技,你需要先得到一串天体密码——它是一个 1∼n 的排列。
天体探测仪允许对于给定的长度 l,返回密码中一个长度为 l 的区间的最小值。
不幸的是,所有长度为 l 的区间最小值混在了一起,你得到的只是 n 个可重集合 S1,…,Sn:
- Si 表示所有长度为 i 的区间最小值构成的可重集合。
你需要根据这些 Si,还原出一种可能的天体密码,保证至少存在一种正确的天体密码。
输入格式
第一行,一个整数 n,表示天体密码的长度。
接下来 n 行,其中第 i 行包含 n−i+1 个整数(长度为 i 的区间共有 n−i+1 个),表示可重集 Si 中的每个元素,注意元素的顺序是任意的,而不一定是按照区间从左到右的顺序。
输出格式
输出一行 n 个整数 p1,p2,…,pn,表示你还原出的天体密码。
如有多种可行解,可以输出任意一种。
提示
【样例 1 解释】
样例输出的天体密码为:p=[3,1,2,4]。
长度为 1 的区间最小值构成的可重集合:S1={3,1,2,4}={4,3,2,1}。
长度为 2 的区间最小值构成的可重集合:S2={min(3,1),min(1,2),min(2,4)}={1,1,2}={1,2,1}。
长度为 3 的区间最小值构成的可重集合:S3={min(3,1,2),min(1,2,4)}={1,1}。
长度为 4 的区间最小值构成的可重集合:S4={min(3,1,2,4)}={1}。
每一个 Si 都与输入对应。
其他可行答案也判为正确,如 p=[4,2,1,3]。
【数据范围】
本题采用捆绑测试。
对于 100% 的数据:2≤n≤800。
子任务编号 |
分值 |
n≤ |
特殊限制 |
1 |
26 |
6 |
无 |
2 |
24 |
16 |
3 |
12 |
800 |
对于每个 i∈[1,n],Si 中不存在两个相同元素 |
4 |
38 |
无 |