There are \(N\) (\(2\le N\le 2\cdot 10^5\)) worlds, each with a portal. Initially,
world \(i\) (for \(1 \leq i \leq N\)) is at \(x\)-coordinate \(i\), and \(y\)-coordinate
\(A_i\) (\(1\le A_i\le 10^9\)). There is also a cow on each world. At time \(0\), all
\(y\)-coordinates are distinct and the worlds start falling: world \(i\) moves
continuously in the negative-\(y\) direction at a speed of \(i\) units per second.

At any time when two worlds are at the same \(y\)-coordinate (possibly a
fractional time), the portals "align", meaning that a cow on one of the worlds
can choose to travel instantaneously to the other world.

For each \(i\), the cow on world \(i\) wants to travel to world \(Q_i\) (\(Q_i\neq i\)).
Help each cow determine how long her journey will take, if she travels
optimally.

Each query output should be a fraction \(a/b\) where \(a\) and \(b\) are positive and
relatively prime integers, or \(-1\) if it the journey is impossible.

Problem credits: Dhruv Rohatgi

SCORING

• Test cases 2-3 satisfy \(N\le 100.\)
• Test cases 4-5 satisfy \(N\le 2000.\)
• Test cases 6-14 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

The first line of input contains a single integer \(N.\)

The next line contains \(N\) space-separated integers \(A_1,A_2,\ldots,A_N.\)

The next line contains \(N\) space-separated integers \(Q_1,Q_2,\ldots,Q_N.\)

Print \(N\) lines, the \(i\)-th of which contains the journey length for cow \(i.\)

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > January > Platinum