Tìm kiếm trên mảng xoay vòng

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm
Points
34
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Một mảng gồm $N$ số nguyên phân biệt ban đầu được sắp xếp tăng dần, sau đó bị xoay vòng tại một vị trí bất kỳ (ví dụ [0, 1, 2, 4, 5, 6, 7] xoay thành [4, 5, 6, 7, 0, 1, 2]). Cho $Q$ truy vấn, mỗi truy vấn là một số $X$, hãy tìm chỉ số (0-indexed) của $X$ trong mảng hoặc in ra -1 nếu không tồn tại, với độ phức tạp $O(\log N)$ cho mỗi truy vấn.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $Q$. Dòng thứ hai chứa $N$ số nguyên của mảng xoay vòng. $Q$ dòng tiếp theo mỗi dòng chứa một số nguyên $X$.

Dữ liệu ra

Gồm $Q$ dòng là kết quả tương ứng.

Ví dụ
Input Output
7 3\n4 5 6 7 0 1 2\n0\n3\n4 4\n-1\n0
1 2\n5\n5\n1 0\n-1
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |X| \le 10^9$.

Draft saved