976 . 閃耀決鬥
TopCoder
.jpg)
Tags
Description
偷摸林事務所（Tomorin プロダクション）是由高松燈（Takamatsu Tomori）所成立的一間偶像事務所，以打磨原石並培養出最閃耀的石頭為目標，全世界的石頭們都以能夠進入該事務所、在舞台上發光發熱為目標而努力著。
這一屆共有 $n$ 顆小石頭參加培訓營，並將在最終選拔後由高松燈社長親自選出最終入選的成員名單。
小石頭們深知社長一向心軟，因此先私下約定好最終名單，準備透過在「閃耀舞台」上決鬥的勝場數來決定去留，好讓社長無須親手淘汰任何石頭。
每顆小石頭都有一個以正整數表示的屬性值 $a_1, a_2, \ldots, a_n$，而兩顆小石頭能夠在閃耀舞台上一決高下。舞台決鬥分為若干回合，在一個回合中：
- 若雙方屬性值 奇偶性相同（同為奇數或同為偶數），立即比較大小並結束決鬥：
- 屬性值較高者獲勝；
- 若屬性值相同則為平手，無石獲勝。
- 否則，屬性值為偶數的一方在本回合視為落敗，下一回合其屬性值將 除以 $2$。
可以證明決鬥途中所有屬性值始終為正整數，且決鬥必定在有限回合內結束。
注意：閃耀舞台的對決僅為模擬，小石頭真正的屬性值 不會 在賽後被修改。
最終選拔即將到來，小石頭們焦頭爛額地發現已經來不及模擬 $\frac{n (n-1)}{2}$ 場決鬥，而你——繪里——身為偷摸林製作的 Producer，在得知小石頭們的決心與困難後，決定協助他們計算 $\text{win}_1, \text{win}_2, \ldots, \text{win}_n$——各自在閃耀舞台中的勝場數，替小石頭們與高松燈社長排憂解難。
Input Format
- line $1$: $\;\; n$
- line $2$: $\;\; a_1 \;\; a_2 \;\; \ldots \;\; a_n$
資料範圍：
- $2 \le n \le 500\,000$。
- $1 \le a_i \le 10^ 9$（$1 \le i \le n$）。
- 輸入的數字均為整數。
Output Format
- line $1$: $\;\; \text{win}_1 \;\; \text{win}_2 \;\; \ldots \;\; \text{win}_n$
Sample Input 1
3 6 7 8
Sample Output 1
0 2 1
Sample Input 2
5 1 2 4 8 16
Sample Output 2
0 0 1 2 3
Sample Input 3
2 1000000000 1000000000
Sample Output 3
0 0
Hints
範例一
該輸入滿足所有子任務的限制。
考慮 $a_1 = 6$ 跟 $a_2 = 7$ 的決鬥：
- $6$ 跟 $7$ 的奇偶性不同，因此偶數的 $6$ 在本回合落敗，變成 $3$。
- $3$ 跟 $7$ 的奇偶性相同，因此數字較大的 $7$ 在本次決鬥獲勝。
考慮 $a_1 = 6$ 跟 $a_3 = 8$ 的決鬥：
- $6$ 跟 $8$ 的奇偶性相同，因此數字較大的 $8$ 在本次決鬥獲勝。
考慮 $a_2 = 7$ 跟 $a_3 = 8$ 的決鬥：
- $7$ 跟 $8$ 的奇偶性不同，因此偶數的 $8$ 在本回合落敗，變成 $4$。
- $7$ 跟 $4$ 的奇偶性不同，因此偶數的 $4$ 在本回合落敗，變成 $2$。
- $7$ 跟 $2$ 的奇偶性不同，因此偶數的 $2$ 在本回合落敗，變成 $1$。
- $7$ 跟 $1$ 的奇偶性相同，因此數字較大的 $7$ 在本次決鬥獲勝。
| 決鬥贏家 | $a_1$ | $a_2$ | $a_3$ |
| $a_1$ | - | $a_2$ | $a_3$ |
| $a_2$ | $a_2$ | - | $a_2$ |
| $a_3$ | $a_3$ | $a_2$ | - |
範例二
該輸入滿足所有子任務的限制。
| 決鬥贏家 | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ |
| $a_1$ | - | 平手 | 平手 | 平手 | 平手 |
| $a_2$ | 平手 | - | $a_3$ | $a_4$ | $a_5$ |
| $a_3$ | 平手 | $a_3$ | - | $a_4$ | $a_5$ |
| $a_4$ | 平手 | $a_4$ | $a_4$ | - | $a_5$ |
| $a_5$ | 平手 | $a_5$ | $a_5$ | $a_5$ | - |
範例三
該輸入滿足子任務 1, 3 的限制。
| 決鬥贏家 | $a_1$ | $a_2$ |
| $a_1$ | - | 平手 |
| $a_2$ | 平手 | - |
Problem Source
YTP 2025 國中組程式挑戰營 p6
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 16~18 | 範例測試資料。 | 0 |
| 2 | 0~5, 16~18 | $n \le 1000$。 | 2 |
| 3 | 6~9, 16~17 | $a_i \le 1000$（$1 \le i \le n$）。 | 5 |
| 4 | 0~18 | 無額外限制。 | 13 |