結果
問題 | 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 = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.readline for _ in range(int(input())): N = int(input()) P = [0] + list(map(int, input().split())) P_ori = P[:] ans = [] ok = 1 for p in range(1, N + 1): for i in range(1, N+1): if P[i] == p: ii = i break if ii == p: continue for i in range(ii - 1, p - 1, -1): j = i while P[j] == j + 1: j -= 1 if j == p - 1: break if 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 = 0 P[jj], P[jj + 1] = P[jj + 1], P[jj] ans.append(i) if P[i] == i or P[i + 1] == i + 1: ok = -1 P[i], P[i + 1] = P[i + 1], P[i] if ok == 1: print(len(ans)) print(*ans) assert len(ans) <= N ** 2 else: print(-1) if ok == 1: for i in ans: assert P_ori[i] != i and P_ori[i + 1] != i + 1 P_ori[i], P_ori[i + 1] = P_ori[i + 1], P_ori[i] assert P_ori == list(range(N + 1)) if __name__ == '__main__': main()