← 返回题目列表

AtCoder · joisc2020_a

A. 建筑装饰4(4号楼)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

ビルの飾りつけ 4 (Building 4) - 原题 PDF 第 1 页
原题PDF第1页
ビルの飾りつけ 4 (Building 4) - 原题 PDF 第 2 页
原题PDF第2页
ビルの飾りつけ 4 (Building 4) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                      Contest Day 1 – Building 4

          ビルの飾り付け4 (Building 4)



  JOI 国では間もなくオリンピックが開催される予定である.世界の選手たちを歓迎するため,空港から宿

泊施設までの道沿いにある高層ビルを飾り付けることにした.飾り付けに利用するビルは2N 個あり,空港

から近い順に1 から2N までの番号が付けられている.

 この飾り付け計画を担当しているK 理事長は,それぞれのビルをどのように飾り付けるかについてJOI

国の国民から公募することにした.その結果,有力な案としてA 案とB 案の2 つの案が最終的に残った.
A 案ではビルi (1 ≦i ≦2N) の飾り付けの豪華さはAi であり,B 案ではビルi の飾り付けの豪華さはBi で

ある.

 どちらの案も捨てがたく,どちらか一方の案に決定してしまうことが極めて難しかったため,それぞれの

ビルについてA 案の飾り付けとB 案の飾り付けのどちらかを採用することですべてのビルの飾り付けを決

めることにした.また,どちらかの案に偏りすぎてしまうと不公平であるので,A 案とB 案からは同じ数

の飾り付けを,すなわちN 個ずつの飾り付けを採用することにした.さらに,空港から宿泊施設に近づく

につれて飾り付けが豪華になってゆくと選手たちが盛り上がると考えられたため,ビルi (1 ≦i ≦2N) に採
用された飾り付けの豪華さをCi としたとき,1 ≦i ≦2N −1 を満たすすべての整数i についてCi ≦Ci+1 が

満たされるようにしたい.

 飾り付けるビルの個数と2 つの案におけるそれぞれのビルの飾り付けの豪華さが与えられたとき,条件を

満たすように飾り付けを選ぶことが可能かどうかを判定し,もし可能であるならばそのような選び方を1 つ

求めるプログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N

      A1 · · · A2N
      B1 · · · B2N


出力

 問題文中の条件を満たすように飾り付けを選ぶことが不可能ならば,標準出力に-1 を出力せよ.

 条件を満たすように飾り付けを選ぶことが可能ならば,標準出力にその選び方を表す長さ2N の文字列S

を1 行に出力せよ.ここで,S のi 文字目(1 ≦i ≦2N) はビルi についてA 案を選ぶときA であり,B 案を

選ぶときB である.条件を満たす選び方が複数存在する場合,そのうちどれを出力してもよい.




                    ビルの飾り付け4– 1 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                      Contest Day 1 – Building 4



制約

    • 1 ≦N ≦500 000.
    • 1 ≦Ai ≦1 000 000 000 (1 ≦i ≦2N).
    • 1 ≦Bi ≦1 000 000 000 (1 ≦i ≦2N).


小課題

    1. (11 点) N ≦2 000.

    2. (89 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   3                              AABABB

   2 5 4 9 15 11

   6 7 6 8 12 14

 飾り付けを順にA 案,A 案,B 案,A 案,B 案,B 案と選ぶと,A 案とB 案からそれぞれ3 つずつの飾

り付けを選んでいる.またこのとき,それぞれのビルの飾り付けの豪華さは順に2, 5, 6, 9, 12, 14 となるの

で,この選び方は問題文中の条件を満たしている.


  入力例2              出力例2

   2                              BBAA

   1 4 10 20

   3 5 8 13

 問題文中の条件を満たすような飾り付けの選び方が複数存在する場合,そのうちどれを出力してもよい.


  入力例3              出力例3

   2                              -1

   3 4 5 6

   10 9 8 7

 問題文中の条件を満たすような飾り付けの選び方は存在しないため,-1 を出力する.




                    ビルの飾り付け4– 2 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                      Spring Training Camp/Qualifying Trial

                                               March 20–23, 2020 (Komaba, Tokyo)


                                                                   Contest Day 1 – Building 4




入力例4                    出力例4

6                                       BABBABAABABA

25 18 40 37 29 95 41 53 39 69 61 90

14 18 22 28 18 30 32 32 63 58 71 78





                  ビルの飾り付け4– 3 / 3