結果

問題 No.1369 交換門松列・竹
ユーザー gew1fw
提出日時 2025-06-12 13:50:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,236 bytes
コンパイル時間 394 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 80,824 KB
最終ジャッジ日時 2025-06-12 13:51:43
合計ジャッジ時間 3,401 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def is_valid(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 main():
    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_triplets = []
        for k in range(N - 2):
            a, b, c = A[k], A[k+1], A[k+2]
            if not is_valid(a, b, c):
                bad_triplets.append(k)
        
        if len(bad_triplets) > 3:
            print("No")
            continue
        
        S = set()
        for k in bad_triplets:
            S.add(k)
            S.add(k + 1)
            S.add(k + 2)
        S = list(S)
        found = False
        
        for i in range(len(S)):
            for j in range(i + 1, len(S)):
                x, y = S[i], S[j]
                if A[x] == A[y]:
                    continue
                
                # Swap
                A[x], A[y] = A[y], A[x]
                
                # Check bad triplets
                valid = True
                for k in bad_triplets:
                    a, b, c = A[k], A[k+1], A[k+2]
                    if not is_valid(a, b, c):
                        valid = False
                        break
                if not valid:
                    A[x], A[y] = A[y], A[x]
                    continue
                
                # Check vicinity triplets
                vicinity = set()
                for pos in [x-1, x, x+1, y-1, y, y+1]:
                    if 0 <= pos < N:
                        vicinity.add(pos)
                
                for pos in vicinity:
                    # Check triplet starting at pos-2
                    k = pos - 2
                    if k >= 0 and k + 2 < N:
                        a, b, c = A[k], A[k+1], A[k+2]
                        if not is_valid(a, b, c):
                            valid = False
                            break
                    if not valid:
                        break
                    # Check triplet starting at pos-1
                    k = pos - 1
                    if k >= 0 and k + 2 < N:
                        a, b, c = A[k], A[k+1], A[k+2]
                        if not is_valid(a, b, c):
                            valid = False
                            break
                    if not valid:
                        break
                    # Check triplet starting at pos
                    k = pos
                    if k + 2 < N:
                        a, b, c = A[k], A[k+1], A[k+2]
                        if not is_valid(a, b, c):
                            valid = False
                            break
                    if not valid:
                        break
                if valid:
                    found = True
                    # Revert swap before breaking
                    A[x], A[y] = A[y], A[x]
                    break
                # Revert swap
                A[x], A[y] = A[y], A[x]
            if found:
                break
        
        print("Yes" if found else "No")

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