結果
問題 | No.1854 Limited Bubble Sort |
ユーザー |
![]() |
提出日時 | 2022-02-25 23:03:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 93 ms / 2,000 ms |
コード長 | 1,503 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 82,392 KB |
実行使用メモリ | 89,472 KB |
最終ジャッジ日時 | 2024-07-03 18:02:51 |
合計ジャッジ時間 | 3,419 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 25 |
ソースコード
mod = 1000000007eps = 10**-9def main():import sysinput = sys.stdin.readlinefor _ in range(int(input())):N = int(input())P = [0] + list(map(int, input().split()))P_ori = P[:]ans = []ok = 1for p in range(1, N + 1):for i in range(1, N+1):if P[i] == p:ii = ibreakif ii == p:continuefor i in range(ii - 1, p - 1, -1):j = iwhile P[j] == j + 1:j -= 1if j == p - 1:breakif j != p - 1 and j != i:for jj in range(j, i):ans.append(jj)if P[jj] == jj or P[jj + 1] == jj + 1:ok = 0P[jj], P[jj + 1] = P[jj + 1], P[jj]ans.append(i)if P[i] == i or P[i + 1] == i + 1:ok = -1P[i], P[i + 1] = P[i + 1], P[i]if ok == 1:print(len(ans))print(*ans)assert len(ans) <= N ** 2else:print(-1)if ok == 1:for i in ans:assert P_ori[i] != i and P_ori[i + 1] != i + 1P_ori[i], P_ori[i + 1] = P_ori[i + 1], P_ori[i]assert P_ori == list(range(N + 1))if __name__ == '__main__':main()