結果

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

ソースコード

diff # 

import sys

def is_valid(a, b, c):
    if a == b or b == c or a == c:
        return False
    return (b > max(a, c)) or (b < min(a, 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) > 5:
            print("No")
            continue
        
        positions = set()
        for k in bad_triplets:
            positions.add(k)
            positions.add(k + 1)
            positions.add(k + 2)
        positions = sorted(positions)
        
        candidates = []
        for i in range(len(positions)):
            for j in range(i + 1, len(positions)):
                a = positions[i]
                b = positions[j]
                if A[a] != A[b]:
                    candidates.append((a, b))
        
        found = False
        original_A = A.copy()
        for a, b in candidates:
            A[a], A[b] = A[b], A[a]
            
            valid = True
            for k in bad_triplets:
                x, y, z = k, k+1, k+2
                if not is_valid(A[x], A[y], A[z]):
                    valid = False
                    break
            if not valid:
                A[a], A[b] = original_A[a], original_A[b]
                continue
            
            affected = set()
            for x in [a, b]:
                for kk in [x - 2, x - 1, x]:
                    if 0 <= kk <= len(A) - 3:
                        affected.add(kk)
            
            for kk in affected:
                x, y, z = kk, kk + 1, kk + 2
                if not is_valid(A[x], A[y], A[z]):
                    valid = False
                    break
            if valid:
                found = True
                break
            
            A[a], A[b] = original_A[a], original_A[b]
        
        print("Yes" if found else "No")

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