Cổng Rơi

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ thế giới. Thế giới $i$ ( $1$ -indexed) bắt đầu tại tọa độ $y = A_{i}$ và rơi xuống với tốc độ $i$ đơn vị/giây (tức là tại thời điểm $t$ , thế giới $i$ ở vị trí $y = A_{i} - i \cdot t$ ).

Khi hai thế giới có cùng tọa độ $y$ tại một thời điểm nào đó (kể cả $t$ là số thực), một cổng dịch chuyển tức thời xuất hiện giữa chúng. Con bò tại thế giới $i$ muốn đến thế giới $Q_{i}$ ( $Q_{i} \neq i$ ) theo thời gian nhỏ nhất (có thể đi qua nhiều thế giới trung gian).

Với mỗi $i$ , in thời gian tối thiểu dưới dạng phân số tối giản $a / b$ (nếu là số nguyên thì in $a / 1$ ), hoặc $- 1$ nếu không thể đến được.

Dữ liệu vào

Dòng 1: $N$ ( $2 \leq N \leq 2 \times 10^{5}$ ).
Dòng 2: $A_{1}, A_{2}, \dots, A_{N}$ ( $1 \leq A_{i} \leq 10^{9}$ ).
Dòng 3: $Q_{1}, Q_{2}, \dots, Q_{N}$ ( $1 \leq Q_{i} \leq N$ , $Q_{i} \neq i$ ).

Dữ liệu ra

$N$ dòng, mỗi dòng là $a / b$ hoặc $- 1$ .

Ví dụ

Input	Output	Giải thích
4 3 5 10 2 3 3 2 1	7/2 7/2 5/1 -1	Bò 1 → thế giới 3: đi qua thế giới 2 (gặp t=1), rồi đến thế giới 3 (gặp t=7/2).

Bình luận

Không có bình luận tại thời điểm này.