結果

問題 No.397 NO MORE KADOMATSU
ユーザー qwewe
提出日時 2025-05-14 13:14:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 3,901 bytes
コンパイル時間 317 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 75,764 KB
平均クエリ数 36.06
最終ジャッジ日時 2025-05-14 13:15:31
合計ジャッジ時間 2,705 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Helper function to read a single integer from standard input
def read_int():
    # Reads a line, removes potential trailing newline/whitespace, converts to int
    return int(sys.stdin.readline().strip()) 

# Helper function to read a list of integers from standard input
def read_int_list():
    # Reads a line, splits by whitespace, converts each part to int, returns as a list
    return list(map(int, sys.stdin.readline().split()))

def solve():
    # Read the size of the sequence, N
    N = read_int()
    # Read the sequence elements into a list A
    A = read_int_list()
    
    # Initialize an empty list to store the swap operations performed.
    # Each swap will be stored as a tuple (index1, index2).
    swaps = []
    
    # Use Selection Sort to sort the array A in non-increasing (descending) order.
    # A sorted array (either non-decreasing or non-increasing) is guaranteed
    # not to contain any Kadomatsu sequence as a contiguous subsegment.
    # The outer loop iterates from i = 0 up to N-2. After iteration i,
    # the element A[i] will be the i-th largest element correctly placed.
    for i in range(N - 1):
        # Find the index of the maximum element in the subarray A[i:] (from index i to the end).
        
        # Start by assuming the maximum element is the one at the current index i.
        max_val = A[i]
        max_idx = i
        
        # Iterate through the rest of the array starting from index i+1.
        for j in range(i + 1, N):
            # If we find an element A[j] that is strictly greater than the current maximum value found so far (max_val).
            if A[j] > max_val:
                # Update the maximum value and the index where it was found.
                max_val = A[j]
                max_idx = j
        
        # After checking the entire subarray A[i:], max_idx holds the index of the maximum element.
        # If the index of the maximum element (max_idx) is different from the current index i,
        # it means the maximum element is not already in its correct sorted position.
        if max_idx != i:
            # Swap the element at index i with the maximum element found at max_idx.
            # This places the maximum element of the suffix A[i:] into position i.
            A[i], A[max_idx] = A[max_idx], A[i]
            # Record this swap operation by adding the pair of indices (i, max_idx) to the swaps list.
            # Note that i and max_idx are guaranteed to be different here.
            swaps.append((i, max_idx))

    # After the loop finishes, the array A is sorted non-increasingly.
    # Now, output the results according to the problem specification.
    
    # Print the total number of swap operations performed.
    print(len(swaps))
    
    # Print each swap operation (u, v) on a separate line.
    # The indices u and v correspond to the positions swapped.
    for u, v in swaps:
        # Use an f-string for formatted output. Prints the two indices separated by a space.
        print(f"{u} {v}")
    
    # Flush the standard output buffer.
    # This is crucial for reactive problems to ensure the judge system receives the output immediately.
    sys.stdout.flush()
    
    # Read the dummy input line required by the reactive judge system.
    # The problem statement says this value will be -1.
    # We must read this line to complete the interaction protocol, although the value itself is not used.
    try:
        # Read the line from standard input. Use '_' as the variable name to indicate the value is intentionally ignored.
      _ = sys.stdin.readline() 
    except EOFError:
        # In case the input stream is closed unexpectedly (e.g., judge terminates communication),
        # catch the EOFError and simply pass, preventing a crash.
      pass 

# Call the main function 'solve()' to execute the solution logic when the script is run.
solve()
0