結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:50:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 252 ms / 2,000 ms
コード長 1,536 bytes
コンパイル時間 353 ms
コンパイル使用メモリ 81,796 KB
実行使用メモリ 125,788 KB
最終ジャッジ日時 2025-06-12 19:51:00
合計ジャッジ時間 6,070 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

def is_rotation(s, t):
    if len(s) != len(t):
        return False
    if len(s) == 0:
        return True

    def compute_lps(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

    concat = t + t
    pattern = s
    lps = compute_lps(pattern)
    i = j = 0
    while i < len(concat):
        if concat[i] == pattern[j]:
            i += 1
            j += 1
            if j == len(pattern):
                return True
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return False

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = list(map(int, data[1:n+1]))
    B = sorted(A)
    
    if A == B:
        print(0)
        return
    
    if is_rotation(B, A):
        print(1)
        return
    
    m = 0
    for k in range(1, n+1):
        if A[-k] == B[-k]:
            m = k
        else:
            break
    
    i = n - m
    if i == 0:
        print(0)
        return
    
    s = B[:i]
    t = A[:i]
    if is_rotation(s, t):
        print(1)
        return
    
    print(2)

if __name__ == "__main__":
    main()
0