離散化 – set/map (AP325 P-2-2C)

1.0s 256M

本題與 P-2-2「離散化 – sort」是同一道題目，但教材在這裡要練習的是用 C++ 的 set／map 來解（P-2-2 用的是排序加二分搜）。兩種寫法都會被接受；測資與 P-2-2 不同。

假設有 \(N\) 個整數要被讀到一個陣列中，我們想要將這些整數置換成從 \(0\) 開始依序排列的整數，並且維持它們原來的大小關係。例如輸入的整數序列是 \((5, 3, 9, 3, 15, 9, 8, 9)\)，這些數由小到大排是 \((3, 3, 5, 8, 9, 9, 9, 15)\)，去除重複者後為 \((3, 5, 8, 9, 15)\)，所以我們要替換的是：

原來的數 替換成
\(3\) \(0\)
\(5\) \(1\)
\(8\) \(2\)
\(9\) \(3\)
\(15\) \(4\)

所以原先的序列就會變成 \((1, 0, 3, 0, 4, 3, 2, 3)\)。

輸入格式

輸入兩行，第一行是正整數 \(N\)，第二行是 \(N\) 個整數，以空白間隔。

限制

  • \(1 \le N \le 10^5\)。
  • 每個整數的絕對值不超過 \(10^9\)。

輸出格式

輸出置換後的序列，兩數之間以一個空白間隔。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

7
0 3 9 3 3 -1 0

範例輸出

1 2 3 2 2 0 1

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 2 章 P-2-2C，第 50 頁（題目敘述同 P-2-2，第 44 頁）；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器（per 帳號 / 題目 / 語言）。
  • 提交 — 把程式碼交給 judge 評測，回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB （約 100 萬字元）
  • 自訂測試與範例測試共用一個沙箱，每人約 3 秒 1 次 （範例測試 1 秒 1 次）
  • 自訂測試與範例測試都有 15 秒 牆鐘上限（正式評測仍依題目原本時限）
  • 互動題不提供自訂測試（無法模擬與 judge 互動）。
  • 提交評測本身沒有 rate limit，但同題短時間內多次提交會被視為刷分。