No.610 Section Award
タグ : / 解いたユーザー数 107
作問者 :
butsurizuki
/ テスター :
はむこ
Remarks
This is the problem for day 10 of Advent Calendar Contest Advent Calendar 2017.
Problem Statement
Butsurizuki-san loves watching ekiden relay races every New Year.
Butsurizuki-san is watching an ekiden competition in which $N$ teams, numbered $1$ to $N$, are participating.
However, because he stayed up watching variety shows on New Year's Eve, he was so tired that he fell asleep while watching the race.
As a result, he slept through an entire section and missed it.
Butsurizuki-san at least wants to know who won the section award for that section.
The section award is given to the runner who ran that section the fastest.
Butsurizuki-san remembers only the following:
・The order in which the teams arrived at the start point of that section: $A_1$ $A_2$ $...$ $A_N$
・The order in which the teams arrived at the goal point of that section: $B_1$ $B_2$ $...$ $B_N$
(There are no ties at either the start or the goal.)
Find all teams whose runner could have won the section award for that section.
Note that retirements, disqualifications, staggered starts for trailing teams, and the like do not occur, so you do not need to take them into account.
Input
$N$ $A_1$ $A_2$ $...$ $A_N$ $B_1$ $B_2$ $...$ $B_N$
The input consists of 3 lines.
The 1st line contains $N$,
the 2nd line contains $A_1$ $A_2$ $...$ $A_N$ separated by spaces, and
the 3rd line contains $B_1$ $B_2$ $...$ $B_N$ separated by spaces.
・Constraints
$1 \le N \le 10^5$
$A_1$ $A_2$ $...$ $A_N$ and $B_1$ $B_2$ $...$ $B_N$ are both permutations of $1$ to $N$.
Output
Output all possible answers, one per line, in ascending order of number.
Sample
Sample 1
Input
5 1 2 3 4 5 4 2 1 3 5
Output
4 5
For example,
Time 100: 1 starts
Time 101: 2 starts
Time 102: 3 starts
Time 103: 4 starts
Time 104: 5 starts
Time 1000: 4 finishes (section time 897)
Time 1010: 2 finishes (section time 909)
Time 1020: 1 finishes (section time 920)
Time 1030: 3 finishes (section time 928)
Time 1040: 5 finishes (section time 936)
in a case like this, 4 wins the section award, and
Time 100: 1 starts
Time 101: 2 starts
Time 102: 3 starts
Time 103: 4 starts
Time 100000: 5 starts
Time 1000: 4 finishes (section time 897)
Time 1010: 2 finishes (section time 909)
Time 1020: 1 finishes (section time 920)
Time 1030: 3 finishes (section time 928)
Time 100001: 5 finishes (section time 1)
in a case like this, 5 wins the section award.
1, 2, and 3 can never win the section award.
Sample 2
Input
5 1 2 3 4 5 5 4 3 2 1
Output
55 overtakes everyone in one sweep to take the lead, and wins the section award without question.
Sample 3
Input
5 1 2 3 4 5 1 2 3 4 5
Output
1 2 3 4 5
There is no movement at all, so there is no telling which team won the section award.
Sample 4
Input
1 1 1
Output
1
One has to question why this competition even exists, but 1 wins the section award.
Sample 5
Input
8 7 1 8 5 4 6 3 2 8 3 6 1 4 5 2 7
Output
2 3 8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。