300308: CF59D. Team Arrangement

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Team Arrangement

题意翻译

## **题目大意** 总共有 $3n$ 名同学,编号为 $1$ ~ $3n$ 将他们分到 $n$ 个小队中,有以下规则: + 显然,每个小队三个成员 + 当某些同学不属于某个团队时,其中得分最高的人选定为新小队的队长 + 新队长从剩下的人中为自己挑选队友 每个人所在的顺序列表被表示为除了他之外其他 $3n-1$ 个同学的排列。 下面给出每个人的得分,这些数字是从 $1$ ~ $3n$ 排列而成的,其中第 $i$ 个数字表示获得了第 $i$ 名的学生人数。 保证没有两个学生共用顺序列表的同一个位置。 您还可以按照创建团队的顺序安排已经组建完成的团队。而你的任务是查询并输出第 $k$ 号学生的优先顺序列表,如果存在多个,请按照字典序输出最小的一个。 ## **输入** 第一行包含一个整数 $n ( 1 \leq n \leq 10^5 )$ ,表示 团队的数量。 第二行包含 $3n$ 个整数 $t ( 1 \leq t \leq 3n )$ ,以空格分开,其中第 $i$ 个数表示第 $i$ 个人的得分。 数据保证每个学生的成绩只出现一次。 接下来是 $n$ 行,每行包括三个数 $x_i$ , $y_i$ , $z_i$ $( 1 \leq x_i,y_i,z_i \leq 3n )$ ,表示一个给定的团队及其成员。其中成员给出的顺序是随意的,但是保证团队本身是按照创建时的顺序给出的,且安排一定是正确的,也就是说每个学生都是一个团队的成员,并且可以使用上面描述的方法创建这些团队。 最后一行包含一个整数 $k( 1 \leq k \leq 3n)$ 。 ## **输出** 一行 $3n-1$ 个数,表示第 $k$ 个学生的优先级按字典序排出的最小的列表。

题目描述

Recently personal training sessions have finished in the Berland State University Olympiad Programmer Training Centre. By the results of these training sessions teams are composed for the oncoming team contest season. Each team consists of three people. All the students of the Centre possess numbers from $ 1 $ to $ 3n $ , and all the teams possess numbers from $ 1 $ to $ n $ . The splitting of students into teams is performed in the following manner: while there are people who are not part of a team, a person with the best total score is chosen among them (the captain of a new team), this person chooses for himself two teammates from those who is left according to his list of priorities. The list of every person's priorities is represented as a permutation from the rest of $ 3n-1 $ students who attend the centre, besides himself. You are given the results of personal training sessions which are a permutation of numbers from $ 1 $ to $ 3n $ , where the $ i $ -th number is the number of student who has won the $ i $ -th place. No two students share a place. You are also given the arrangement of the already formed teams in the order in which they has been created. Your task is to determine the list of priorities for the student number $ k $ . If there are several priority lists, choose the lexicographically minimal one.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1<=n<=10^{5} $ ) which is the number of resulting teams. The second line contains $ 3n $ space-separated integers from $ 1 $ to $ 3n $ which are the results of personal training sessions. It is guaranteed that every student appears in the results exactly once. Then follow $ n $ lines each containing three integers from $ 1 $ to $ 3n $ — each line describes the members of a given team. The members of one team can be listed in any order, but the teams themselves are listed in the order in which they were created. It is guaranteed that the arrangement is correct, that is that every student is a member of exactly one team and those teams could really be created from the given results using the method described above. The last line contains number $ k $ ( $ 1<=k<=3n $ ) which is the number of a student for who the list of priorities should be found.

输出格式


Print $ 3n-1 $ numbers — the lexicographically smallest list of priorities for the student number $ k $ . The lexicographical comparison is performed by the standard < operator in modern programming languages. The list $ a $ is lexicographically less that the list $ b $ if exists such an $ i $ ( $ 1<=i<=3n $ ), that $ a_{i}&lt;b_{i} $ , and for any $ j $ ( $ 1<=j&lt;i $ ) $ a_{j}=b_{j} $ . Note, that the list 1 9 10 is lexicographically less than the list 1 10 9. That is, the comparison of lists is different from the comparison of lines.

输入输出样例

输入样例 #1

3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
4

输出样例 #1

2 3 5 6 9 1 7 8 

输入样例 #2

3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
8

输出样例 #2

1 2 3 4 5 6 7 9 

输入样例 #3

2
4 1 3 2 5 6
4 6 5
1 2 3
4

输出样例 #3

5 6 1 2 3 

Input

题意翻译

## **题目大意** 总共有 $3n$ 名同学,编号为 $1$ ~ $3n$ 将他们分到 $n$ 个小队中,有以下规则: + 显然,每个小队三个成员 + 当某些同学不属于某个团队时,其中得分最高的人选定为新小队的队长 + 新队长从剩下的人中为自己挑选队友 每个人所在的顺序列表被表示为除了他之外其他 $3n-1$ 个同学的排列。 下面给出每个人的得分,这些数字是从 $1$ ~ $3n$ 排列而成的,其中第 $i$ 个数字表示获得了第 $i$ 名的学生人数。 保证没有两个学生共用顺序列表的同一个位置。 您还可以按照创建团队的顺序安排已经组建完成的团队。而你的任务是查询并输出第 $k$ 号学生的优先顺序列表,如果存在多个,请按照字典序输出最小的一个。 ## **输入** 第一行包含一个整数 $n ( 1 \leq n \leq 10^5 )$ ,表示 团队的数量。 第二行包含 $3n$ 个整数 $t ( 1 \leq t \leq 3n )$ ,以空格分开,其中第 $i$ 个数表示第 $i$ 个人的得分。 数据保证每个学生的成绩只出现一次。 接下来是 $n$ 行,每行包括三个数 $x_i$ , $y_i$ , $z_i$ $( 1 \leq x_i,y_i,z_i \leq 3n )$ ,表示一个给定的团队及其成员。其中成员给出的顺序是随意的,但是保证团队本身是按照创建时的顺序给出的,且安排一定是正确的,也就是说每个学生都是一个团队的成员,并且可以使用上面描述的方法创建这些团队。 最后一行包含一个整数 $k( 1 \leq k \leq 3n)$ 。 ## **输出** 一行 $3n-1$ 个数,表示第 $k$ 个学生的优先级按字典序排出的最小的列表。

加入题单

上一题 下一题 算法标签: