問題一覧 > 通常問題

No.1913 Periodic Comparison

レベル : / AI推定難易度 : 2500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : chineristAC / テスター : 37zigen tokusakurai
お気に入りにしたユーザー ProblemId : 7209 / 自分の提出
問題文最終更新日: 2022-04-09 00:00:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 340 (順位表) の他の問題:

Problem Statement

There is a map $f$ from non-negative integers to non-negative integers. This map has the following properties.

  • $f$ is a bijection. That is, $i\neq j$ implies $f(i)\neq f(j)$, and for any non-negative integer $i$ there exists a non-negative integer $j$ such that $f(j)=i$.
  • For any pair of non-negative integers $i,\ j\ (i\neq j)$, $f(i) < f(j) \iff f(i+N) < f(j+N)$ holds.

Currently, it is known that $f(NX_i+i)=Y_i$ for $N$ non-negative integers $X_i\ (0\le i < N)$.

Find $1$ possible set of values for $f(0),\ f(1),\ \dots,\ f(N-1)$. If no $f$ satisfying the conditions exists, print $-1$.

Input

$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$
  • All input values are integers.

Output

If an $f$ satisfying the conditions exists, output in the following format. If there are multiple possible sets of values for $f(0),\ f(1),\ \dots,\ f(N-1)$, you may output any of them.

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

If none exists, print $-1$.

Print a newline at the end.

Sample

Sample 1
Input
3
1 2 3
3 7 11
Output
0 1 2

The map $f$ such that $f(i)=i$ holds for any non-negative integer $i$ satisfies the conditions.

Sample 2
Input
2
2 4
5 7
Output
-1

Sample 3
Input
10
19415 8780 38491 29861 14770 83188 8287 132281 46613 30704
607321 71929 305933 781336 273477 768910 54260 673443 992574 322283
Output
431453 45589 74510 487097 170087 109744 34795 0 526444 116316

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