結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0