CSES 3140 - Inversion Sorting

1.0s 512M

有一個隱藏的排列 \(a_1, a_2,\dots, a_n\)，它是整數 \(1, 2,\dots, n\) 的一個排列。你的任務是透過反轉連續子陣列把這個排列排好。

每一回你可以反轉這個排列的一段連續子陣列。之後你會被告知這個排列目前的逆序數量。如果逆序數量是 \(0\)（也就是這個排列已經排好了），你就獲勝。

這是一道互動題。你的程式透過標準輸入與標準輸出和評測程式互動。一開始你要先讀入一個整數 \(n\)：排列的長度。

輪到你時，輸出兩個整數 \(i\) 和 \(j\)：反轉下標 \(i\) 到 \(j\) 之間的連續子陣列。

之後，下一行輸入會有一個整數：這次操作之後的逆序數量。如果這個數字是 \(0\)，你就獲勝，而且你的程式必須在這之後結束。

說明：這裡一開始的排列是 \([3,1,2]\)。第一次操作之後排列變成 \([1,3,2]\)，逆序數量是 \(1\)。第二次操作之後排列變成 \([1,2,3]\)，逆序數量是 \(0\)。

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。

題目頁說明