問題一覧 > 通常問題

No.610 区間賞(Section Award)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 104
作問者 : butsurizukibutsurizuki / テスター : はむこはむこ
7 ProblemId : 2035 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-05 23:56:22

備考

これは、Advent Calendar Contest Advent Calendar 2017の10日目用の問題です。

問題文

物理好きさんは、毎年正月に駅伝を見るのが大好きです。
物理好きさんは$1$~$N$の$N$チームが出場する駅伝大会を見ています。
しかし、彼は大晦日にバラエティーを見てしまったため疲労が溜まっており駅伝を見ている途中に寝てしまいました。
そして、ある区間を丸ごと寝て見逃してしまいました。
物理好きさんは、せめてその区間の区間賞を誰が取ったのか知りたがっています。
区間賞とは、その区間を最も速く走った選手に与えられる賞です。
物理好きさんは、
・その区間のスタート地点における各チームの到着順 $A_1$ $A_2$ $...$ $A_N$
・その区間のゴール地点における各チームの到着順 $B_1$ $B_2$ $...$ $B_N$
のみを記憶しています。(スタート、ゴールともに同着はありません)
その区間の区間賞を獲った選手のチームとしてあり得るものを全て求めてください。
但し、リタイア、失格、繰り上げスタートなどは発生しないので考慮に入れなくても構いません。

入力

$N$
$A_1$ $A_2$ $...$ $A_N$
$B_1$ $B_2$ $...$ $B_N$

入力は3行からなり、 1行目に $N$ が、
2行目に $A_1$ $A_2$ $...$ $A_N$ が空白区切りで、
3行目に $B_1$ $B_2$ $...$ $B_N$ が空白区切りで与えられます。
・制約
$1 \le N \le 10^5$
$A_1$ $A_2$ $...$ $A_N$ , $B_1$ $B_2$ $...$ $B_N$ は双方とも$1$~$N$ の順列

出力

解としてありえるものを1行に1つずつ、番号の若い方から出力してください。

サンプル

サンプル1
入力
5
1 2 3 4 5
4 2 1 3 5
出力
4
5

例えば、
時刻100 1スタート
時刻101 2スタート
時刻102 3スタート
時刻103 4スタート
時刻104 5スタート

時刻1000 4ゴール(区間記録897)
時刻1010 2ゴール(区間記録909)
時刻1020 1ゴール(区間記録920)
時刻1030 3ゴール(区間記録928)
時刻1040 5ゴール(区間記録936)

のようなケースなら4が区間賞、

時刻100 1スタート
時刻101 2スタート
時刻102 3スタート
時刻103 4スタート
時刻100000 5スタート

時刻1000 4ゴール(区間記録897)
時刻1010 2ゴール(区間記録909)
時刻1020 1ゴール(区間記録920)
時刻1030 3ゴール(区間記録928)
時刻100001 5ゴール(区間記録1)

のようなケースなら5が区間賞です。
1,2,3が区間賞であることはありません。

サンプル2
入力
5
1 2 3 4 5
5 4 3 2 1
出力
5

5がゴボウ抜きで総捲り、文句なしで区間賞です。

サンプル3
入力
5
1 2 3 4 5
1 2 3 4 5
出力
1
2
3
4
5

全く動きがなく、何処が区間賞なのかさっぱり分かりません。

サンプル4
入力
1
1
1
出力
1

もはや大会の存在意義を疑いますが、1が区間賞です。

サンプル5
入力
8
7 1 8 5 4 6 3 2
8 3 6 1 4 5 2 7
出力
2
3
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。