結果

問題 No.1369 交換門松列・竹
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:36:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,511 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 79,736 KB
最終ジャッジ日時 2025-04-16 15:41:01
合計ジャッジ時間 3,177 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

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 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 i in range(N-2):
            a, b, c = A[i], A[i+1], A[i+2]
            if not is_kadomatsu(a, b, c):
                bad_triplets.append(i)
        
        K = len(bad_triplets)
        if K > 5:
            print("No")
            continue
        
        S = set()
        for i in bad_triplets:
            S.add(i)
            S.add(i+1)
            S.add(i+2)
        S_list = sorted(S)
        found = False
        
        for i in range(len(S_list)):
            x = S_list[i]
            for j in range(i+1, len(S_list)):
                y = S_list[j]
                if A[x] == A[y]:
                    continue
                # Swap x and y
                A[x], A[y] = A[y], A[x]
                
                # Check original bad triplets
                valid = True
                for idx in bad_triplets:
                    a, b, c = A[idx], A[idx+1], A[idx+2]
                    if not is_kadomatsu(a, b, c):
                        valid = False
                        break
                if not valid:
                    A[x], A[y] = A[y], A[x]
                    continue
                
                # Check triplets around x and y
                triplets_to_check = set()
                for pos in [x, y]:
                    for delta in [-2, -1, 0]:
                        start = pos + delta
                        if 0 <= start <= N-3:
                            triplets_to_check.add(start)
                # Check each triplet
                for start in triplets_to_check:
                    a, b, c = A[start], A[start+1], A[start+2]
                    if not is_kadomatsu(a, b, c):
                        valid = False
                        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