結果
問題 |
No.1425 Yet Another Cyclic Shifts Sorting
|
ユーザー |
![]() |
提出日時 | 2025-06-12 19:56:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,307 bytes |
コンパイル時間 | 186 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 111,400 KB |
最終ジャッジ日時 | 2025-06-12 19:57:06 |
合計ジャッジ時間 | 6,076 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 TLE * 1 -- * 23 |
ソースコード
def main(): import sys input = sys.stdin.read().split() n = int(input[0]) A = list(map(int, input[1:n+1])) sorted_A = sorted(A) if A == sorted_A: print(0) return # Precompute suffix match suff_match = [False] * (n + 2) suff_match[n] = (A[n-1] == sorted_A[n-1]) for i in range(n-1, 0, -1): suff_match[i] = (A[i-1] == sorted_A[i-1]) and suff_match[i+1] # Find all i where suff_match[i+1] is True for i in range(n, 0, -1): if i + 1 > n: match = True else: match = suff_match[i+1] if match: X = A[:i] Y = sorted_A[:i] # Check if Y is a rotation of X # Create concatenated string for KMP concat = X + X found = False for k in range(i): if concat[k] == Y[0]: match = True for j in range(1, i): if concat[k + j] != Y[j]: match = False break if match: found = True break if found: print(1) return print(2) if __name__ == "__main__": main()