COCI 2016/2017 - Contest 6 - Turnir

View as PDF

Submit solution

Points: 0.50 (partial)
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 6
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Jozef được tặng một dãy số có ~2^N~ số nguyên dương. Vì Jozef hay tham gia các giải đấu bóng đá, cậu muốn tổ chức một giải đấu cho ~2^N~ số nguyên dương này.

Giải đấu của các số nguyên dương được biểu diễn như sau:

Hình ảnh trên là giải đấu với ~N = 4~.

Giải đấu sẽ có ~N + 1~ cấp độ từ ~0~ đến ~N~.

Đầu tiên, ban tổ chức aka Jozef sẽ chia các số vào ~2^N~ vị trí ở cấp độ thứ ~N~. Sau đó, mỗi khi ~2~ số gặp nhau ở cấp độ thứ ~i~, số lớn hơn sẽ được lên cấp độ thứ ~i - 1~. Trong trường hợp cả ~2~ số bằng nhau, Jozef có thể chọn ~1~ trong ~2~ số. Chẳng hạn, Jozef có thể chọn tùy ý ~1~ trong ~2~ số ~8~ ở cấp độ ~1~ để lên cấp độ ~0~.

Với việc phải work hard make money, Jozef không có đủ thời gian để tổ chức tất cả các giải đấu có thể. Cậu muốn biết: Với mỗi số trong dãy số hiện tại, cấp độ cao nhất (cấp độ có số thứ tự bé nhất) mà số đó có thể lên được trong tất cả các cách chia các số vào ~2^N~ vị trí.

Input

Dòng đầu tiên chứa số nguyên dương ~N (1 \le N \le 20)~.

Dòng tiếp theo chứa ~2^N~ số nguyên dương trong đoạn ~[1, 10^9]~ - dãy số mà Jozef được tặng.

Output

~2^N~ số trên một dòng, số thứ ~i~ là cấp độ cao nhất mà số thứ ~i~ có thể lên được.

Sample Input 1

2
1 4 3 2

Sample Output 1

2 0 1 1

Sample Input 2

4
5 3 2 6 4 8 7 1 2 4 3 3 6 4 8 1 

Sample Output 2

1 2 2 1 1 0 1 3 2 1 2 2 1 1 0 3

Sample Input 3

1
1 1 

Sample Output 3

0 0

Giải thích test đề thứ nhất

  • Số ~1~ sẽ không bao giờ lên được cấp độ ~0~ hay cấp độ ~1~ vì ở cấp độ ~2~ số ~1~ phải gặp ~1~ trong ~3~ số ~2, 3, 4~, và cả ~3~ số này đều lớn hơn ~1~.
  • Số ~4~ sẽ luôn luôn lên được cấp độ ~0~ vì ở cả ~2~ cấp độ ~1~ và ~2~, ~4~ chỉ phải gặp các số ~1, 2, 3~ đều là những số bé hơn ~4~.
  • Số ~2~ và ~3~ có thể lên được cấp độ ~1~ nếu gặp ~1~ ở cấp độ ~1~.
  • Số ~2~ và ~3~ không thể lên được cấp độ ~0~ vì nếu lên cấp độ ~1~ thì chắc chắn sẽ gặp ~4~, mà cả ~2~ và ~3~ đều bé hơn ~4~.

Do đó, cấp độ cao nhất mà ~1~ lên được là ~2~, ~2~ và ~3~ là ~1~ và ~4~ là ~0~.

Giải thích test đề thứ ba

  • Như đã nói, cả ~2~ số ~1~ đều có thể được Jozef chọn để lên cấp độ ~0~. Điều này cũng có nghĩa là cấp độ cao nhất mà ~2~ số này có thể đạt đến là ~0~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.