Bedao OI Contest 2 - Khoảng Cách Ngắn Nhất
View as PDF
Submit solution
Points:
0.50 (partial)
Time limit:
2.0s
Memory limit:
256M
Input:
mind.inp
Output:
mind.out
Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho số nguyên dương ~n~ và dãy số nguyên không âm ~a_1,a_2,...,a_n~. Ta định nghĩa khoảng cách giữa hai số ~x~ và ~y~ là số lần ít nhất phải thực hiện các thao tác sau để biến ~x~ thành ~y~:
Chọn một lũy thừa của ~2~, kí hiệu là ~2^z~.
Thực hiện phép gán ~x = x~ ~\oplus~ ~2^z~
Trong đó ~\oplus~ là phép toán ~XOR~ được cho bởi bảng giới đây:
| ~x~ | ~y~ | ~x~ ~\oplus~ ~y~ |
|---|---|---|
| ~0~ | ~0~ | ~0~ |
| ~0~ | ~1~ | ~1~ |
| ~1~ | ~0~ | ~1~ |
| ~1~ | ~1~ | ~0~ |
Việc thực hiện phép ~XOR~ trên hai số nguyên là thực hiện phép ~XOR~ trên từng bit trong biểu diễn nhị phân của hai số.
Yêu cầu: Với mỗi số ~a_1,a_2,...,a_n~; hãy tìm một số khác trong dãy có khoảng cách tới số đó là bé nhất.
Input
Vào từ file văn bản mind.inp:
- Dòng đầu tiên chứa số nguyên dương ~n~ (~2\le n \le 5 \times 10^5~) là số phần tử của dãy.
- Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,...,a_n~ (~a_i \le 5 \times 10^5~) mô tả dãy được cho.
Output
Đưa ra file văn bản mind.out:
- ~n~ số nguyên, mỗi số nguyên là khoảng cách gần nhất ứng với một phần tử trong phương án tối ưu tìm được.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~n \le 5000~ |
| 2 | ~20\%~ | ~a_i \le 100~ với mọi ~i~ |
| 3 | ~30\%~ | ~n,a_i\le 5 \times 10^4~ với mọi ~i~ |
| 4 | ~30\%~ | Không có ràng buộc gì thêm |
Sample Input 1
6
1 2 4 3 8 15
Sample Output 1
1 1 2 1 2 2
Comments
Hà Ly là của t