結果

問題 No.1425 Yet Another Cyclic Shifts Sorting
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:21:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 1,679 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 82,472 KB
実行使用メモリ 118,460 KB
最終ジャッジ日時 2025-05-14 13:24:24
合計ジャッジ時間 6,664 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))

    # According to constraints, N >= 2.
    S = sorted(A)

    if A == S:
        print(0)
        return

    # Find L, the length of the prefix A[0...L-1] that differs from S[0...L-1].
    # L will be > 0 because A != S.
    # As argued, if N >= 2 and A != S, then L >= 2.
    L = N
    while L > 0 and A[L-1] == S[L-1]:
        L -= 1
    
    P = A[:L]       # The prefix of A that needs to be sorted
    S_P = S[:L]     # The target sorted prefix

    # Convert lists to comma-separated strings to check for cyclic shift.
    # This handles elements with multiple digits correctly.
    # P and S_P are guaranteed to be non-empty because L >= 2.
    s_P_str = ",".join(map(str, P))
    s_S_P_str = ",".join(map(str, S_P))

    # Check if S_P is a cyclic shift of P by looking for S_P_str
    # in the string s_P_str + "," + s_P_str.
    # This concatenated string contains all (L) cyclic shifts of P.
    # Example: P=[1,2,3] -> s_P_str="1,2,3"
    # combined = "1,2,3,1,2,3".
    # Shifts "1,2,3", "2,3,1", "3,1,2" are all in combined.
    
    # Note: Since A != S, L >= 2. This means P != S_P.
    # So, if s_S_P_str is found in (s_P_str + "," + s_P_str),
    # it means S_P is a non-trivial cyclic shift of P, or S_P is P itself
    # (if the first check A==S was not there).
    # Given A != S, P will not be identical to S_P unless L becomes 0.
    # Here, L is the length of the prefix that *still needs sorting*.
    # So P is by definition not S_P.
    
    if s_S_P_str in (s_P_str + "," + s_P_str):
        print(1)
    else:
        print(2)

solve()
0