QOJ.ac

QOJ

実行時間制限: 1.0 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓

#17774. 年鑑整理

統計

題目背景

茶話會臨近尾聲,作為慶典十週年專屬的懷舊環節,小 T 特意找出了歷屆 THUPC 的珍貴檔案——一排記錄了十年點滴的賽事年鑑,供大家傳閱。

翻閱過後,兩人準備將年鑑放回書架。由於歲月流逝,年鑑的破損度參差不齊。心思細膩的小 S 提議,在放回時將它們按破損度嚴格遞增重新排序,以此直觀地展現時間沉澱的痕跡。然而,年鑑的紙張已經十分脆弱,每次只能極其小心地將其中的一本向前平移一位,且這無可避免地會略微增加該年鑑的破損度。更棘手的是,留給他們的整理時間十分有限。小 S 想知道,能否在有限的操作次數內,將這些年鑑放回書架並整理得井然有序呢?

書架上擺放著 $n$ 本年鑑。初始時,第 $i$ ($1 \le i \le n$) 本年鑑的破損度為 $a_i$。

每次移動時,首先需要選擇一個位置 $p$ ($1 \le p \le n - 1$),然後將第 $p + 1$ 本年鑑向前移動至第 $p$ 本年鑑前,移動後它的破損度將會增加 $1$。

由於時間有限,總共只能進行不超過 $n^2 - n$ 次移動。作為眾多翻閱年鑑的參與者之一,你需要幫助小 S 規劃出一組具體的移動方案,使得最終書架上的年鑑破損度從左到右嚴格遞增。

輸入格式

每個測試點中包含多組測試數據。輸入的第一行包含一個正整數 $T$ ($1 \le T \le 10$),表示數據組數。對於每組測試數據:

  • 第一行包含一個正整數 $n$ ($2 \le n \le 500$),表示年鑑的數量。
  • 第二行包含 $n$ 個正整數 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$),分別表示初始時每一本年鑑的破損度。

輸出格式

對於每組測試數據,若存在可行的移動方案:

  • 第一行輸出一個非負整數 $k$ ($0 \le k \le n^2 - n$),表示移動次數。
  • 第二行輸出 $k$ 個正整數 $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n - 1$),分別表示每次移動選定的位置。

若無法使得最終書架上的年鑑破損度從左到右嚴格遞增,則僅輸出一行一個整數 $-1$。

範例

輸入格式 1

3
2
2 2
2
2 1
3
4 5 1

輸出格式 1

0

-1
2
2 1

說明

對於第一組測試數據,初始時書架上的年鑑破損度從左到右就是嚴格遞增的。

對於第二組測試數據,可以證明,無法在 $n^2 - n$ 次移動內使得最終書架上的年鑑破損度從左到右嚴格遞增。

對於第三組測試數據,一種可行的移動方案如下:

  • 第一次移動選擇位置 $2$,所有年鑑的破損度變為 $[4, 2, 5]$;
  • 第二次移動選擇位置 $1$,所有年鑑的破損度變為 $[3, 4, 5]$。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.