UOJ Logo

NOI.AC

1S 256MB

#298. 归并

统计

题目描述

所谓的“归并”,就是把多个有序数组合并为一个有序数组的操作,本题就是要实现这个操作。 某中学初一有$n$个班级,第$i$个班级有$a_i$位同学,现在每个班的同学都已经在各自班级门口按身高从小到大排成了一队,现在作为精通编程的你要指挥这$n$条队伍中的所有人排成一队,排成的新队伍需要满足$3$个条件:

1、按照身高从小到大顺序;

2、如果身高相同,按照班级编号小的在前,例如$1$班身高$160$的同学需要排在$2$班身高$160$的同学前面;

3、如果班级编号也相同,按照他们在原来队伍中的顺序排列,例如$2$位$1$班身高$160$的同学$a$和$b$,在原先队伍中$a$在$b$前面,则新队伍中$a$还在$b$前面。

排队操作是这样进行的:老师给你了这$n$条队伍的信息,你从$1$班到$n$班叫出所有班级队伍的第一位同学,找出其中身高最小的,让他成为新队伍的第一位;接着该同学原先队伍中的后面一位同学代替他成为那条队伍中的第一位;接着你继续找出所有队伍第一位中身高最小的同学,让他成为新队伍的第二位…………这样的操作一直进行下去,直到所有同学都进入新队伍

例如: 有三条队伍

1班:140,150,160
2班:150,160,165
3班:155,157,166

你首先选择1班140,2班150,3班155中最小的1班140,然后1班150同学就代替140同学成为第一位,接着你在1班150,2班150,3班155同学中选择最小的1班150(相同身高班级编号小优先)…………最后新队伍就变成140,1班150,2班150,155,157,1班160,2班160,165,166,完成排序工作。

现在老师不想知道新队伍中每位同学的身高,他只想知道每位同学的做操优美度,请你将结果汇报给他。

输入格式

输入第一行一个数$n$,表示班级的数量; 接下来第二行,$n$个数$a[i]$,表示每个班级的人数; 接下来$n$行,每行$a_i$个数,表示i班队伍中的身高顺序h_{ij},已经按照身高从小到大; 接下来$n$行,每行$a_i$个数,表示i班队伍中每位同学的做操优美度$v_{ij}$,与身高顺序一一对应。

输出格式

输出1行,按顺序输出新队伍中每个同学的做操优美度,用空格隔开。

输入样例1

3
3 3 3
140 150 160
150 160 165
155 157 166
1 3 5
2 4 5
5 2 4

输出样例1

1 3 2 5 2 5 4 5 4

数据范围

对于$20%$的数据,$n=2,1 \leq a_i \leq 1000$;

对于$60%$的数据,$1 \leq a[i] \leq 100000$;

对于$100%$的数据,$1 \leq n \leq 4,1 \leq a_i \leq 700000,1 \leq h_{ij} \leq1000,1 \leq v_{ij} \leq 9$。