結果
問題 |
No.1051 PQ Permutation
|
ユーザー |
![]() |
提出日時 | 2020-05-14 19:03:57 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 333 ms / 2,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 211 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 30,996 KB |
最終ジャッジ日時 | 2024-09-15 13:23:15 |
合計ジャッジ時間 | 7,758 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import sys import bisect read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N, P, Q = map(int, readline().split()) A = [0] + list(map(int, read().split())) def next_perm(A): B = [A.pop()] while A[-1] > B[-1]: B.append(A.pop()) x = A.pop() i = bisect.bisect_left(B, x) A.append(B[i]) B[i] = x A += B return A def solve(A, P, Q): next_perm(A) if A[0]: return False p = A.index(P) q = A.index(Q) if p < q: return A if max(A[q:]) == Q: second = max(A[q + 1:]) q -= 1 while Q != A[q] > second: second = A[q] q -= 1 A = A[:q + 1] + sorted(A[q + 1:], reverse=True) return solve(A, P, Q) A = A[:q + 1] + sorted(A[q + 1:], reverse=True) next_perm(A) p = A.index(P) q = A.index(Q) if p < q: return A if P > Q: del A[q] A.insert(p, Q) return A return solve(A, P, Q) A = solve(A, P, Q) if not A or A[0] != 0: print(-1) else: print(*A[1:])