問題一覧 > 通常問題

No.1913 Periodic Comparison

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 12
作問者 : chineristACchineristAC / テスター : 37zigen37zigen tokusakuraitokusakurai
6 ProblemId : 7209 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-09 00:00:57

問題文

非負整数から非負整数への写像 $f$ があります。この写像は以下の性質を持ちます。

  • $f$ は全単射写像である。すなわち、 $i\neq j$ ならば $f(i)\neq f(j)$ が成り立ち、任意の非負整数 $i$ に対しある非負整数 $j$ が存在して $f(j)=i$ が成り立つ。
  • 任意の非負整数の組 $i,\ j\ (i\neq j)$ に対し $f(i) < f(j) \iff f(i+N) < f(j+N)$ が成り立つ

現在、 $N$ 個の非負整数 $X_i\ (0\le i < N)$ に対し $f(NX_i+i)=Y_i$ であることがわかっています。

$f(0),\ f(1),\ \dots,\ f(N-1)$ として考えられるものを $1$ つ求めてください。条件を満たす $f$ が存在しない場合は $-1$ を出力してください。

入力

$N$
$X_0$ $X_1$ $\dots$ $X_{N-1}$
$Y_0$ $Y_1$ $\dots$ $Y_{N-1}$
  • $1 \le N \le 2\times 10^5$
  • $0 \le X_i,\ Y_i \le 10^6$
  • 与えられる入力はすべて整数

出力

条件を満たす $f$ が存在する場合は以下の形式で出力してください。 $f(0),\ f(1),\ \dots,\ f(N-1)$ として考えられるものが複数存在する場合はいずれを出力してもかまいません。

$f(0)$ $f(1)$ $\dots$ $f(N-1)$

存在しない場合は $-1$ と出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3
1 2 3
3 7 11
出力
0 1 2

任意の非負整数 $i$ に対し $f(i)=i$ が成り立つ写像 $f$ が条件を満たします。

サンプル2
入力
2
2 4
5 7
出力
-1

サンプル3
入力
10
19415 8780 38491 29861 14770 83188 8287 132281 46613 30704
607321 71929 305933 781336 273477 768910 54260 673443 992574 322283
出力
431453 45589 74510 487097 170087 109744 34795 0 526444 116316

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