結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:32:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,304 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 90,416 KB
最終ジャッジ日時 2025-03-31 17:33:27
合計ジャッジ時間 9,452 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 8 TLE * 2 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

def is_kadomatsu(a, b, c):
    if a == b or b == c or a == c:
        return False
    return (b > a and b > c) or (b < a and b < c)

def solve():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    for _ in range(T):
        N = int(input[ptr])
        ptr +=1
        A = list(map(int, input[ptr:ptr+N]))
        ptr +=N
        
        BAD = []
        for s in range(N-2):
            a = A[s]
            b = A[s+1]
            c = A[s+2]
            if not is_kadomatsu(a, b, c):
                BAD.append(s)
        
        # If no BAD, which is impossible
        if not BAD:
            print("No")
            continue
        
        # Collect all positions in BAD triplets
        S = set()
        for s in BAD:
            S.add(s)
            S.add(s+1)
            S.add(s+2)
        S = list(S)
        possible = False
        
        # Iterate all possible pairs in S
        for i_idx in range(len(S)):
            i = S[i_idx]
            for j_idx in range(i_idx+1, len(S)):
                j = S[j_idx]
                if A[i] == A[j]:
                    continue
                
                # Check if all BAD triplets include i or j
                all_included = True
                for s in BAD:
                    triplet_includes = False
                    for pos in [s, s+1, s+2]:
                        if pos == i or pos == j:
                            triplet_includes = True
                            break
                    if not triplet_includes:
                        all_included = False
                        break
                if not all_included:
                    continue
                
                # Perform swap and check
                A[i], A[j] = A[j], A[i]
                
                # Check BAD triplets are now valid
                valid_bad = True
                for s in BAD:
                    a_vals = A[s]
                    b_vals = A[s+1]
                    c_vals = A[s+2]
                    if not is_kadomatsu(a_vals, b_vals, c_vals):
                        valid_bad = False
                        break
                if not valid_bad:
                    A[i], A[j] = A[j], A[i]
                    continue
                
                # Check all triplets involving i or j's positions
                valid = True
                checked = set()
                for x in [i, j]:
                    for s in [x-2, x-1, x]:
                        if s <0 or s+2 >= N:
                            continue
                        if s not in checked:
                            checked.add(s)
                            a = A[s]
                            b = A[s+1]
                            c = A[s+2]
                            if not is_kadomatsu(a, b, c):
                                valid = False
                                break
                    if not valid:
                        break
                # Revert swap
                A[i], A[j] = A[j], A[i]
                
                if valid:
                    possible = True
                    break
            if possible:
                break
        
        print("Yes" if possible else "No")

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