No.1913 Periodic Comparison
タグ : / 解いたユーザー数 12
作問者 :
37zigen
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もしくは右上の雲マークをクリックしてアカウントを作成してください。