結果

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

ソースコード

diff # 

import sys

def is_kadomatsu(a, b, c):
    if a == b or a == c or b == c:
        return False
    return (b == max(a, b, c)) or (b == min(a, b, c))

def get_affected_triplets(i, n):
    triplets = []
    # Check triplet starting at i-2
    s = i - 2
    if s >= 0 and s + 2 < n:
        triplets.append(s)
    # Check triplet starting at i-1
    s = i - 1
    if s >= 0 and s + 2 < n:
        triplets.append(s)
    # Check triplet starting at i
    s = i
    if s + 2 < n:
        triplets.append(s)
    return triplets

def solve():
    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
        # Find all invalid triplets
        S = []
        for s in range(N - 2):
            a, b, c = A[s], A[s+1], A[s+2]
            if not is_kadomatsu(a, b, c):
                S.append(s)
        # If there are more than 4 invalid triplets, it's impossible
        if len(S) > 4:
            print("No")
            continue
        # Collect all positions in invalid triplets
        positions = set()
        for s in S:
            positions.add(s)
            positions.add(s + 1)
            positions.add(s + 2)
        positions = list(positions)
        found = False
        # Check all pairs of positions
        for i in range(len(positions)):
            for j in range(i + 1, len(positions)):
                x = positions[i]
                y = positions[j]
                if A[x] == A[y]:
                    continue
                # Check if all triplets in S contain x or y
                valid = True
                for s in S:
                    triplet_pos = [s, s+1, s+2]
                    if x not in triplet_pos and y not in triplet_pos:
                        valid = False
                        break
                if not valid:
                    continue
                # Perform swap
                A[x], A[y] = A[y], A[x]
                # Collect all triplets to check
                triplets_to_check = set()
                # Check triplets involving x
                for s in get_affected_triplets(x, N):
                    triplets_to_check.add(s)
                # Check triplets involving y
                for s in get_affected_triplets(y, N):
                    triplets_to_check.add(s)
                # Check all these triplets
                ok = True
                for s in triplets_to_check:
                    a = A[s]
                    b_val = A[s+1]
                    c = A[s+2]
                    if not is_kadomatsu(a, b_val, c):
                        ok = False
                        break
                if ok:
                    found = True
                    # Undo swap before returning
                    A[x], A[y] = A[y], A[x]
                    print("Yes")
                    break
                # Undo swap
                A[x], A[y] = A[y], A[x]
            if found:
                break
        if found:
            continue
        else:
            print("No")

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