結果

問題 No.1371 交換門松列・松
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:25:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,679 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,248 KB
実行使用メモリ 76,596 KB
最終ジャッジ日時 2025-05-14 13:26:12
合計ジャッジ時間 7,781 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    def is_kadomatsu_triplet(v1, v2, v3):
        # All elements in A are distinct, so if indices are distinct, values are distinct.
        # When B[k-1], B[k], B[k+1] are formed, their original values from A are distinct
        # as they come from distinct positions in A (unless i or j maps to one of k-1,k,k+1
        # and results in using the same value A[original_pos] multiple times through B).
        # However, B is also a permutation of 1..N, so B[idx1], B[idx2], B[idx3]
        # for distinct idx1,idx2,idx3 will always be distinct values.
        return (v2 > v1 and v2 > v3) or (v2 < v1 and v2 < v3)

    count = 0
    
    # Create a mutable copy for swapping
    B = list(A)

    # Iterate over all pairs (i, j) with i < j
    for i in range(N):
        for j in range(i + 1, N):
            # Perform swap
            B[i], B[j] = A[j], A[i] # B[i] gets A[j]
            # B[j] gets A[i]
            # Other elements B[k] = A[k] for k != i, j

            current_swap_valid = True
            
            # Determine affected middle indices m_idx for B
            # m_idx is such that (B[m_idx-1], B[m_idx], B[m_idx+1]) is checked.
            # m_idx ranges from 1 to N-2.
            
            # A position p (0 to N-1) is involved in a triplet check with middle m_idx if
            # p = m_idx-1, p = m_idx, or p = m_idx+1.
            # This means m_idx can be p+1, p, or p-1.
            # The values at positions i and j in A are swapped.
            # So we need to check triplets where B[m_idx-1], B[m_idx], or B[m_idx+1]
            # corresponds to original positions i or j.
            
            indices_to_check_middle = set()
            # Consider position i being involved
            if i - 1 >= 1 and i - 1 <= N - 2: # i is B[m_idx+1], m_idx = i-1
                indices_to_check_middle.add(i - 1)
            if i >= 1 and i <= N - 2:     # i is B[m_idx], m_idx = i
                indices_to_check_middle.add(i)
            if i + 1 >= 1 and i + 1 <= N - 2: # i is B[m_idx-1], m_idx = i+1
                indices_to_check_middle.add(i + 1)
            
            # Consider position j being involved
            if j - 1 >= 1 and j - 1 <= N - 2: # j is B[m_idx+1], m_idx = j-1
                indices_to_check_middle.add(j - 1)
            if j >= 1 and j <= N - 2:     # j is B[m_idx], m_idx = j
                indices_to_check_middle.add(j)
            if j + 1 >= 1 and j + 1 <= N - 2: # j is B[m_idx-1], m_idx = j+1
                indices_to_check_middle.add(j + 1)
            
            if N < 3: # No triplets to check
                 current_swap_valid = True # Or false depending on problem for N<3, but N>=3 stated, N>=5 for constraints
            elif not indices_to_check_middle and N >= 3:
                # This can happen if N is small and i, j are such that no existing middle elements are affected.
                # e.g. N=3, swap (0,1). A[0],A[1],A[2]. Middle A[1].
                # B[0]=A[1], B[1]=A[0], B[2]=A[2].
                # Affected middle: i=0 -> m_idx=0+1=1. j=1 -> m_idx=1-1=0 (invalid), m_idx=1, m_idx=1+1=2 (invalid).
                # So check m_idx=1. (B[0], B[1], B[2]).
                # This means indices_to_check_middle will generally not be empty if N>=3.
                # If N=5, $A_0 \dots A_4$. Middle indices $1,2,3$.
                # if $i=0, j=4$. Affected $m$: $i+1=1$. $j-1=3$. Check $m=1,3$.
                pass # This case should be covered by set logic.

            for m_idx in indices_to_check_middle:
                # Construct triplet from B using values from A.
                # B[m_idx-1]
                val_m_minus_1 = A[m_idx-1]
                if m_idx - 1 == i: val_m_minus_1 = A[j]
                elif m_idx - 1 == j: val_m_minus_1 = A[i]
                
                # B[m_idx]
                val_m = A[m_idx]
                if m_idx == i: val_m = A[j]
                elif m_idx == j: val_m = A[i]

                # B[m_idx+1]
                val_m_plus_1 = A[m_idx+1]
                if m_idx + 1 == i: val_m_plus_1 = A[j]
                elif m_idx + 1 == j: val_m_plus_1 = A[i]

                if not is_kadomatsu_triplet(val_m_minus_1, val_m, val_m_plus_1):
                    current_swap_valid = False
                    break
            
            if current_swap_valid:
                count += 1
            
            # No need to swap back B to A's state because B is not used across (i,j) iterations.
            # The logic for fetching values for B[x] directly uses A and the swapped values A[i], A[j].
            
    print(count)

solve()
0