RiseOJ – 떨어지는 포털

설명

포털이 하나씩 있는 $$N$$ 개( $2\le N\le 2\cdot 10^5$ )의 세계가 있다. 처음에 세계 $$i$$ ( $1 \leq i \leq N$ )는 $$x$$ 좌표 $$i$$ , $$y$$ 좌표 $$A_i$$ ( $1\le A_i\le 10^9$ )에 있다. 각 세계에는 소도 한 마리씩 있다. 시각 $$0$$ 에 모든 $$y$$ 좌표는 서로 다르며, 세계들이 떨어지기 시작한다. 세계 $$i$$ 는 초당 $$i$$ 단위의 속력으로 $$y$$ 축 음의 방향으로 연속적으로 이동한다.

두 세계가 같은 $$y$$ 좌표에 있게 되는 어느 시점(분수 시각일 수도 있다)에든 포털이 "정렬"되며, 이는 두 세계 중 한쪽에 있는 소가 순간적으로 다른 세계로 이동하기로 선택할 수 있음을 뜻한다.

각 $$i$$ 에 대해, 세계 $$i$$ 에 있는 소는 세계 $$Q_i$$ ( $Q_i\neq i$ )로 가고 싶어 한다. 각 소가 최적으로 이동할 때 여정에 얼마나 걸리는지 구하도록 도와주자.

각 쿼리의 출력은 $$a$$ 와 $$b$$ 가 서로소인 양의 정수인 분수 $$a/b$$ 형태여야 하며, 여정이 불가능하다면 $$-1$$ 을 출력한다.

문제 제공: Dhruv Rohatgi

제약

점수 배점

테스트 케이스 2-3은 $N\le 100$ 을 만족한다.
테스트 케이스 4-5는 $N\le 2000$ 을 만족한다.
테스트 케이스 6-14는 추가 제약이 없다.

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 정수 $$N$$ 이 주어진다.

다음 줄에 공백으로 구분된 $$N$$ 개의 정수 $A_1,A_2,\ldots,A_N$ 이 주어진다.

다음 줄에 공백으로 구분된 $$N$$ 개의 정수 $Q_1,Q_2,\ldots,Q_N$ 이 주어진다.

출력 형식

$$N$$ 개의 줄을 출력하며, $$i$$ 번째 줄에는 소 $$i$$ 의 여정 길이를 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 falling.in · 출력을 쓸 파일 falling.out

예제 1

입력

4
3 5 10 2
3 3 2 1

출력

7/2
7/2
5/1
-1

설명

Consider the answer for the cow originally on world 2. At time $$2$$ worlds 1 and
2 align, so the cow can travel to world 1. At time $\frac{7}{2}$ worlds 1 and 3
align, so the cow can travel to world 3.

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

떨어지는 포털

평가 및 의견

풀이 제출